Linear Hadwiger's conjecture
Let be the complete graph on vertices, and call a graph -minor-free if it has no minor. A graph is -colourable if it has a proper colouring using at most colours. Linear Hadwiger's conjecture. There exists a constant such that for every integer , every -minor-free graph is -colourable. This is a natural weakening of Hadwiger's conjecture. The best known general upper bounds are superlinear, so the conjecture remains open.
References
7 papers in this index state this conjecture (2011–2022). The statement above is taken from the most recent of them; the others are arXiv:2110.09403, arXiv:2108.01633, arXiv:2010.05999, arXiv:2004.10367, arXiv:1910.09378, arXiv:1110.2272.
Source: Yangyan Gu, Yiting Jiang, David R. Wood and Xuding Zhu, “Refined list version of Hadwiger's conjecture”, arXiv:2209.07013 (2022).
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.