Plummer–Stiebitz–Toft reformulation for independence number two

About 2 years old · traced to

Let GG be an nn-vertex graph with independence number α(G)\alpha(G). Let KrK_r denote the complete graph on rr vertices.

Plummer–Stiebitz–Toft conjecture. Every nn-vertex graph GG with α(G)≤2\alpha(G)\leq2 contains K⌈n/2⌉K_{\lceil n/2\rceil} as a minor.

The paper states this as a reformulation of Hadwiger's conjecture for graphs with independence number at most two. A general proof is not known; the paper records a weaker K⌈n/3⌉K_{\lceil n/3\rceil} minor result as evidence for it.

References

Primary source

Rong Chen and Zijian Deng, “Seymour and Woodall's conjecture holds for graphs with independence number two”, arXiv:2406.02643 (2025).

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.