Back to search

Central Florida

Coloring Graphs with Forbidden Minors

Abstract

dc:description.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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rolek, Martin
Contributors dc:contributor
  • Song, Zixia

Subjects

dc:subject × 1

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0006649

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
related terms
citation

Rolek, Martin. Coloring Graphs with Forbidden Minors. https://stars.library.ucf.edu/etd/5400