Central Florida
Extremal Functions for Kt-s Minors and Coloring Graphs with No Kt-s Minors
Abstract
dc:description.abstractHadwiger's Conjecture from 1943 states that every graph with no Kt minor is (t-1)-colorable; it remains wide open for t ≥ 7. For positive integers t and s, let Kt-s denote the family of graphs obtained from the complete graph Kt by removing s edges. We say that a graph has no Kt-s minor if it has no H minor for every H in Kt-s. In 1971, Jakobsen proved that every graph with no K7-2 minor is 6-colorable. In this dissertation, we first study the extremal functions for K8-4 minors, K9-6 minors, and K10-12 minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K8-4 minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K9-6 minor, and every graph on n ≥ 10 vertices with at least 5.5n-17.5 edges has a K10-12 minor. We then prove that every graph with no K8-4 minor is 7-colorable, every graph with no K9-6 minor is 8-colorable, and every graph with no K10-12 minor is 9-colorable. The proofs use the extremal functions as well as generalized Kempe chains of contraction-critical graphs obtained by Rolek and Song and a method for finding minors from three different clique subgraphs, originally developed by Robertson, Seymour, and Thomas in 1993 to prove Hadwiger's Conjecture for t = 6. Our main results imply that H-Hadwiger's Conjecture is true for each graph H on 8 vertices that is a subgraph of every graph in K8-4, each graph H on 9 vertices that is a subgraph of every graph in K9-6, and each graph H on 10 vertices that is a subgraph of every graph in K10-12.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lafferty, Michael M
- Contributors dc:contributor
-
- Song, Zixia
Subjects
dc:subject × 5Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- DP0028050