Clique immersions in graphs with certain forbidden subgraphs

Daniel A. Quiroz

Published 2020-04-11Version 1

The Lescure-Meyniel conjecture is the analogue of Hadwiger's conjecture for the immersion order. It states that every graph $G$ contains the complete graph $K_{\chi(G)}$ as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph $G$ with independence number $\alpha(G)\ge 2$ and no hole of length between $4$ and $2\alpha(G)$ satisfies this conjecture. In particular, every $C_4$-free graph $G$ with $\alpha(G)= 2$ satisfies the Lescure-Meyniel conjecture. We give another generalisation of this corollary, as follows. Let $G$ and $H$ be graphs with independence number at most 2, such that $|V(H)|\le 4$. If $G$ is $H$-free, then $G$ satisfies the Lescure-Meyniel conjecture.