Weak Hadwiger conjecture for graphs with independence number at most two
Let be a finite simple graph, let denote its independence number, and let denote the complete graph on vertices. A graph is a minor of if it can be obtained by deleting vertices or edges and contracting edges.
Weak Hadwiger conjecture. Every graph with contains
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
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.