Current Search: Rolek, Martin (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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor 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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in the process giving a shorter and computerfree 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 Ktminors is true. Additionally, we show that any graph with no K8?minor is 9colorable, and any graph with no K8?minor is 8colorable. The Kempechain method developed for our proofs of the above results may be of independent interest. We also use Mader's HWege theorem to establish some sufficient conditions for a graph to contain a K8minor.Another motivation for my research is a wellknown conjecture of Erd?s and Lov(&)#225;sz from 1968, the DoubleCritical Graph Conjecture. A connected graph G is doublecritical if for all edges xy ? E(G), ?(G  x  y) = ?(G)  2. Erd?s and Lov(&)#225;sz conjectured that the only doublecritical tchromatic 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 noncomplete, doublecritical, tchromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computerfree proof for t = 8, and extend the result to show that G contains a K9minor for all t ? 9. Finally, we show that the DoubleCritical Graph Conjecture is true for doublecritical graphs with chromatic number t ? 8 if such graphs are clawfree.
Show less

Date Issued

2017

Identifier

CFE0006649, ucf:51227

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0006649