Weak Hadwiger conjecture for graphs with independence number at most two

About 16 years old · traced to

Let GG be a finite simple graph, let α(G)\alpha(G) denote its independence number, and let KnK_n denote the complete graph on nn vertices. A graph HH is a minor of GG if it can be obtained by deleting vertices or edges and contracting edges.

Weak Hadwiger conjecture. Every graph GG with α(G)≤2\alpha(G)\leq 2 contains

K⌈∣V(G)∣2⌉K_{\left\lceil\frac{|V(G)|}{2}\right\rceil}

as a minor.

Plummer, Stiebitz, and Toft showed that this conjecture is equivalent to Hadwiger's conjecture for graphs with independence number at most two. It remains unsolved and is presented as a possible route toward understanding, or disproving, Hadwiger's conjecture.

References

Primary source

Rong Chen and Zijian Deng, “Connected matching in graphs with independence number two”, arXiv:2409.05920 (2024).

Additional references

3 papers in this index state this conjecture (2010–2024). The statement above is taken from the most recent of them; the others are arXiv:2109.10240, arXiv:1005.5194.

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.