Vergara's conjecture for graphs with independence number two

From papers

Let GG be a graph with independence number α(G)=2\alpha(G)=2, let χ(G)\chi(G) denote its chromatic number, and let Kχ(G)K_{\chi(G)} be the complete graph on χ(G)\chi(G) vertices. A weak immersion of a graph HH in GG consists of an injection from V(H)V(H) to V(G)V(G) and pairwise edge-disjoint paths in GG representing the edges of HH. Vergara's conjecture. Every graph GG with α(G)=2\alpha(G)=2 contains a weak immersion of Kχ(G)K_{\chi(G)}. The source presents this as the Abu-Khzam–Langston conjecture restricted to graphs of independence number two and notes its equivalence, for graphs with α(G)2\alpha(G)\leq 2, to the corresponding assertion involving KV(G)/2K_{\lceil |V(G)|/2\rceil}. The status of this named formulation is not separately established in the supplied text.

Progress summary

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

Sources & referencesView supporting material

Primary source

Jonathan C. Dahlke, “The Abu-Khzamx2013Langston Conjecture for Graphs with α(G) = 2”, arXiv:2605.28159 (2026).

Additional references

5 papers in this index state this conjecture (2020–2026). The statement above is taken from the most recent of them; the others are arXiv:2605.04022, arXiv:2412.04522, arXiv:2303.06483, arXiv:2004.05433.

Solutions 0

No solutions have been posted yet.