Publication Date
5-2013
Advisor(s)
Karen L. Collins
Department
Mathematics
Language
English
Abstract
A classic question in graph theory is: Does a graph with chromatic number d "contain" a complete graph on d vertices in some way? In this dissertation we will explore some attempts to answer this question and will focus on the containment called immersion. In 2003 Abu-Khzam and Langston conjectured that every d- chromatic graph contains an immersion of K_{d}. This conjecture is true for d ≤ 6 by the work of Lescure and Meyniel in 1989 and for d ≤ 7 by the work of DeVos, Kawarabayashi, Mohar, and Okamura in 2010. In each case the conjecture was proved by proving the stronger statement that graphs with minimum degree d – 1 contain immersions of K_{d}. DeVos, Dvořák, Fox, McDonald, Mohar, and Scheide show this statement fails for d = 10 and d ≥ 12. In this dissertation we show that the stronger statement is false for d ≥ 8 and give infinite families of examples with minimum degree d – 1 and chromatic number d – 3, d – 2, or d – 1 that do not contain an immersion of K_{d}. Our examples can be up to (d – 2)-edge-connected. We show, using Hajós' Construction, that there is an infinite class of non-(d – 1)- colorable graphs that contain an immersion of K_{d}. We conclude with some open questions, and the conjecture that a graph G with minimum degree d – 1 and more than
|V (G)|
----------------------
m(d+1) – (d – 2)
vertices of degree at least md has an immersion of K_{d}.
Recommended Citation
Heenehan, Megan Elizabeth, "Chromatic Number and Immersions of Complete Graphs" (2013). Dissertations. 22.
http://wesscholar.wesleyan.edu/etd_diss/22
© Copyright is owned by author of this document