Current Search: vertex coloring -- double-critical graphs -- claw-free graphs -- graph minors -- Hadwiger's conjecture (x)
-
-
Title
-
Coloring graphs with forbidden minors.
-
Creator
-
Rolek, Martin, Song, Zixia, Brennan, Joseph, Reid, Michael, Zhao, Yue, DeMara, Ronald, University of Central Florida
-
Abstract / Description
-
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 K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in...
Show moreA 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 K_t-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 K8?-minor is 9-colorable, and any graph with no K8?-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 Erd?s and Lov(&)#225;sz 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. Erd?s and Lov(&)#225;sz 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.
Show less
-
Date Issued
-
2017
-
Identifier
-
CFE0006649, ucf:51227
-
Format
-
Document (PDF)
-
PURL
-
http://purl.flvc.org/ucf/fd/CFE0006649
