Immersing small complete graphs

Matt DeVoss, Ken-ichi Kawarabayashi, Bojan Mohar, Haruko Okamura


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


Immersion, Hadwiger Conjecture

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications