Biclique immersions in graphs with independence number 2 (Q6612311)

To split off a pair of adjacent edges \(uv, vw\) (with \(u\), \(v\), \(w\) distinct) amounts to deleting those two edges and adding an edge joining \(u\) to \(v\) (keeping parallel edges if needed). A graph \(G\) is said to contain an immersion of another graph \(H\) if \(H\) can be obtained from a subgraph of \(G\) by splitting off pairs of edges and deleting isolated vertices. Notice then that if \(G\) contains \(H\) as a subdivision, it contains \(H\) as an immersion (and as a minor). The main contribution of this paper is the following result, which states that graphs with independence number 2 contain an immersion of every complete bipartite graph on \(\lceil n/2\rceil\) vertices: Let \(G\) be an \(n\)-vertex graph with independence number 2, and \(\ell \leq \lceil n/2\rceil-1\) be a positive integer. Then \(G\) contains an immersion of \(K_{\ell,\lceil n/2 \rceil -\ell}\). An open question concludes the paper.