Linear Hadwiger's conjecture

About 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

Primary source

Yangyan Gu, Yiting Jiang, David R. Wood and Xuding Zhu, “Refined list version of Hadwiger's conjecture”, arXiv:2209.07013 (2022).

Additional 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.

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.