Weak Hadwiger conjecture for graphs with independence number at most two
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.
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
Sign in to submit a solution.
No solutions have been posted yet.