Biclique immersions in graphs with independence number 2
European Journal of Combinatorics, 2024•Elsevier
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.
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.
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.
Elsevier