Back to search

Central Florida

Extremal Functions for Kt-s Minors and Coloring Graphs with No Kt-s Minors

Abstract

dc:description.abstract

Hadwiger'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 × 5

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
DP0028050

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lafferty, Michael M. Extremal Functions for Kt-s Minors and Coloring Graphs with No Kt-s Minors. https://stars.library.ucf.edu/etd2023/66