Chromatic Number and Immersions of Complete Graphs

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 dchromatic 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řak, 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 Hajos’ 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.