Clique immersion in graphs without fixed bipartite graph

Abstract

A graph $G$ contains $H$ as an \emph{immersion} if there is an injective mapping $\varphi :V(H)\to V(G)$ such that for each edge $uv\in E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $\varphi (u)$ and $\varphi (v)$, and all the paths $P_{uv}$, $uv\in E(H)$, are pairwise edge-disjoint. An analogue of Hadwiger's conjecture for the clique immersions by Lescure and Meyniel, and independently by Abu-Khzam and Langston, states that every graph $G$ contains $K_{\chi (G)}$ as an immersion. We prove that for any constant $\epsilon >0$ and integers $s,t\ge 2$, there exists $d_0=d_0(\epsilon ,s,t)$ such that every $K_{s,t}$-free graph $G$ with $d(G)\ge d_0$ contains a clique immersion of order $(1-\epsilon )d(G)$. This implies that the above-mentioned conjecture is asymptotically true for graphs without a fixed complete bipartite graph.

2 figures

References in corpus (1)

• Further progress towards Hadwiger's conjecture