Clique immersions and independence number
2019
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 $\bigl\lceil \frac{\chi (G)-4}{3.54}\bigr\rceil$ vertices. Their result implies that every $n$-vertex graph with independence number $\alpha$ contains an immersion of a clique on $\bigl\lceil \frac{n}{3.54\alpha}-1.13\bigr\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 $\bigl\lfloor \frac {4n}{9 (\alpha -1)} \bigr\rfloor - \lfloor \frac{\alpha}2 \rfloor$ vertices.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
6
Citations
NaN
KQI