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χ(G) . For graphs with independence number 2, this is equivalent to stating that every such n-vertex graph contains an immersion of K⌈n/2⌉. We show that every n-vertex graph with independence number 2 contains every complete bipartite graph on ⌈n/2⌉ vertices as an immersion.