← All problems

Linear Hadwiger's conjecture

15 years old · traced to

Let KtK_t be the complete graph on tt vertices, and call a graph KtK_t-minor-free if it has no KtK_t minor. A graph is kk-colourable if it has a proper colouring using at most kk colours. Linear Hadwiger's conjecture. There exists a constant C>0C>0 such that for every integer t⩾1t\geqslant1, every KtK_t-minor-free graph is CtCt-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

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.