Abstract

The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph K-t(+1) as an immersion satisfies chi(G) <= t. If true, this conjecture would imply that every graph with n vertices and independence number alpha contains K (inverted right perpendicular n/alpha inverted left perpendicular )as an immersion (and if alpha = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of Kt+1-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing K(t+1 )as an immersion satisfies chi(G) <= 3.54t + 7. Their result implies that any graph with n vertices and independence number alpha contains K inverted right perpendicular n/3.54 alpha -c inverted (left perpendicular) as an immersion, where c < 1.98. Moreover, the same authors prove that every graph of independence number 2 contains K-2 left perpendicular n/5 right perpendicular as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least left perpendicular 2n/9 right perpendicular -1 vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least left perpendicular 4n/27 right perpendicular -1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.