Botler et al.'s bipartite minor conjecture for independence number two

At least 1 year old · documented by

Let GG be an nn-vertex graph with independence number α(G)\alpha(G). For positive integers ℓ\ell and rr, let Kℓ,rK_{\ell,r} denote the complete bipartite graph with parts of sizes ℓ\ell and rr.

Botler et al.'s conjecture. Let GG be an nn-vertex graph with α(G)≤2\alpha(G)\leq2. For any positive integer ℓ\ell with ℓ<⌈n/2⌉\ell<\lceil n/2\rceil, we have

G⪰mKℓ,⌈n/2⌉−ℓ.G\succeq_m K_{\ell,\lceil n/2\rceil-\ell}.

The source describes this as slightly weaker than the Plummer–Stiebitz–Toft reformulation. It remains open in the generality stated, while the paper proves a related stronger-looking result for the graphs under consideration.

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.