Constructing Graphs with No Immersion of Large Complete Graphs

In 1989, Lescure and Meyniel proved, for d = 5 , 6 , that every d ‐chromatic graph contains an immersion of K d , and in 2003 Abu‐Khzam and Langston conjectured that this holds for all d . In 2010, DeVos, Kawarabayashi, Mohar, and Okamura proved this conjecture for d = 7 . In each proof, the d ‐chromatic assumption was not fully utilized, as the proofs only use the fact that a d ‐critical graph has minimum degree at least d − 1 . DeVos, Dvořák, Fox, McDonald, Mohar, and Scheide show the stronger conjecture that a graph with minimum degree d − 1 has an immersion of K d fails for d = 10 and d ≥ 12 with a finite number of examples for each value of d , and small chromatic number relative to d , but it is shown that a minimum degree of 200 d does guarantee an immersion of K d .In this paper, we show that the stronger conjecture is false for d = 8 , 9 , 11 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 that two of Hajós' operations preserve immersions of K d . We conclude with some open questions, and the conjecture that a 2‐edge‐connected graph G with minimum degree d − 1 and more than| V ( G ) | m ( d + 1 ) − ( d − 2 )vertices of degree at least m d has an immersion of K d .