Vergara's conjecture for graphs with independence number two

About 6 years old · traced to

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 K⌈∣V(G)∣/2⌉K_{\lceil |V(G)|/2\rceil}. The status of this named formulation is not separately established in the supplied text.

References

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.

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.