The analogue of Hadwigers 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 nalpharceil}$ 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 $bigllceil frac{chi (G)-4}{3.54}bigrrceil$ vertices. Their result implies that every $n$-vertex graph with independence number $alpha$ contains an immersion of a clique on $bigllceil frac{n}{3.54alpha}-1.13bigrrceil$ vertices. We improve on this result for all $alphage 3$, by showing that every $n$-vertex graph with independence number $alphage 3$ contains an immersion of a clique on $bigllfloor frac {n}{2.25 alpha - f(alpha)} bigrrfloor - 1$ vertices, where $f$ is a nonnegative function.
Download