Publication Date



Karen L. Collins






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 Kd. 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 Kd. 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 Kd. 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 Kd. 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 Kd.



© Copyright is owned by author of this document