Plummer–Stiebitz–Toft reformulation for independence number two

From papers

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 Kn/2K_{\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 Kn/3K_{\lceil n/3\rceil} minor result as evidence for it.

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

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

Solutions 0

No solutions have been posted yet.