Abstract

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t − 1)-colorable. This conjecture has been proved true for t ≤ 6, but remains open for all t ≥ 7. For t = 7, it is not even yet known if a graph with no K7-minor is 7-colorable. We begin by showing that every graph with no Kt-minor is (2t − 6)- colorable for t = 7, 8, 9, in the process giving a shorter and computer-free proof of the known results for t = 7, 8. We also show that this result extends to larger values of t if Mader's bound for the extremal function for Kt-minors is true. Additionally, we show that any graph with no K−8 - minor is 9-colorable, and any graph with no K=8-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use Mader's H-Wege theorem to establish some sufficient conditions for a graph to contain a K8-minor. Another motivation for my research is a well-known conjecture of Erdos and Lovasz from 1968, the Double-Critical Graph Conjecture. A connected graph G is double-critical if for all edges xy ∈ E(G), χ(G−x−y) = χ(G)−2. Erdos and Lovasz conjectured that the only double-critical t-chromatic graph is the complete graph Kt. This conjecture has been show to be true for t ≤ 5 and remains open for t ≥ 6. It has further been shown that any non-complete, double-critical, t-chromatic graph contains Kt as a minor for t ≤ 8. We give a shorter proof of this result for t = 7, a computer-free proof for t = 8, and extend the result to show that G contains a K9-minor for all t ≥ 9. Finally, we show that the Double-Critical Graph Conjecture is true for double-critical graphs with chromatic number t ≤ 8 if such graphs are claw-free.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2017

Semester

Spring

Advisor

Song, Zixia

Degree

Doctor of Philosophy (Ph.D.)

College

College of Sciences

Department

Mathematics

Degree Program

Mathematics

Format

application/pdf

Identifier

CFE0006649

URL

http://purl.fcla.edu/fcla/etd/CFE0006649

Language

English

Release Date

May 2017

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Download

Included in

Mathematics Commons

Share

COinS
 

Accessibility Statement

This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.