Half-order immersion conjecture for graphs with independence number at most two

Let GG be a graph on nn vertices, and let α(G)\alpha(G) denote its independence number. An immersion of a graph HH in GG is a subgraph obtainable from GG by lifting edges and deleting vertices and/or edges. Half-order immersion conjecture. Any graph GG with α(G)2\alpha(G) \leq 2 contains an immersion of Kn/2K_{\lceil n/2 \rceil}. Since every color class has at most two vertices in such a graph, this conjecture is the natural half-order consequence of Abu-Khzam–Langston's restricted conjecture. The source proves that this statement is equivalent, for this graph class, to the restricted Abu-Khzam–Langston conjecture, but leaves both statements unresolved in general.

Sources & referencesView supporting material

Primary source

Sylvia Vergara, “Complete graph immersions in dense graphs”, arXiv:1502.01786 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.