Clique immersions and independence number

Abstract

The analogue of Hadwiger's conjecture for the immersion order states that every graph $G$ contains $K_{\chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $\alpha$ contains $K_{\lceil \frac{n}{\alpha }\rceil }$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $\lceil \frac{\chi (G)-4}{3.54}\rceil$ vertices. Their result implies that every $n$-vertex graph with independence number $\alpha$ contains an immersion of a clique on $\lceil \frac{n}{3.54\alpha }-1.13\rceil$ vertices. We improve on this result for all $\alpha \ge 3$, by showing that every $n$-vertex graph with independence number $\alpha \ge 3$ contains an immersion of a clique on $\lfloor \frac{n}{2.25\alpha -f(\alpha )}\rfloor -1$ vertices, where $f$ is a nonnegative function.

13 pages, 1 figure. Minor changes according to referees' suggestions

References in corpus (2)

• Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor
• Further progress towards Hadwiger's conjecture

Cited by in corpus (1)

• Clique immersions in graphs of independence number two with certain forbidden subgraphs