Biclique immersions in graphs with independence number 2

Abstract

The analogue of Hadwiger's conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{\ddot{I}‡(G)}$. For graphs with independence number 2, this is equivalent to stating that every such $n$-vertex graph contains an immersion of $K_{\lceil n/2\rceil }$. We show that every $n$-vertex graph with independence number 2 contains every complete bipartite graph on $\lceil n/2\rceil$ vertices as an immersion.

21 pages, 11 figures