Immersions of large cliques in graphs with independence number 2 and bounded maximum degree

Abstract

An immersion of a graph $H$ in a graph $G$ is a minimal subgraph $I$ of $G$ for which there is an injection $\mathrm{i}:V(H)\to V(I)$ and a set of edge-disjoint paths $\{P_e:e\in E(H)\}$ in $I$ such that the end vertices of $P_{uv}$ are precisely $\mathrm{i}(u)$ and $\mathrm{i}(v)$. The immersion analogue of Hadwiger Conjecture (1943), posed by Lescure and Meyniel (1985), asks whether every graph $G$ contains an immersion of $K_{\chi (G)}$. Its restriction to graphs with independence number 2 has received some attention recently, and Vergara (2017) raised the weaker conjecture that every graph with independence number 2 has an immersion of $K_{\chi (G)}$. This implies that every graph with independence number 2 has an immersion of $K_{\lceil n/2\rceil }$. In this paper, we verify Vergara Conjecture for graphs with bounded maximum degree. Specifically, we prove that if $G$ is a graph with independence number $2$, maximum degree less than $2n/3-1$ and clique covering number at most $3$, then $G$ contains an immersion of $K_{\chi (G)}$ (and thus of $K_{\lceil n/2\rceil }$). Using a result of Jin (1995), this implies that if $G$ is a graph with independence number $2$ and maximum degree less than $19n/29-1$, then $G$ contains an immersion of $K_{\chi (G)}$ (and thus of $K_{\lceil n/2\rceil }$).

15 pages, 3 figures