Immersing small complete graphs

Abstract

Following in the spirit of the Hadwiger and Hajós conjectures, Abu-Khzam and Langston have conjectured that every k -chromatic graph contains an immersion of K k . They proved this for k ≤ 4. Much before that, Lescure and Meyniel [F. Lescure and H. Meyniel, On a problem upon configurations contained in graphs with given chromatic number, Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), 325−331, Ann. Discrete Math. 41, North-Holland, Amsterdam, 1989] obtained a stronger result that included also the values k = 5 and 6, by proving that every simple graph of minimum degree k − 1 contains an immersion of K k . They noted that they also have a proof of the same result for k = 7 but have not published it due to the length of the proof. We give a simple proof of this result. This, in particular, proves the conjecture of Abu-Khzam and Langston for every k ≤ 7.