Weak Hadwiger conjecture for graphs with independence number at most two

From papers

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

KV(G)2K_{\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.

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, “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.

Solutions 0

No solutions have been posted yet.