The 3/23/2-List Hadwiger conjecture

About 15 years old · traced to

Let t∈Nt\in\mathbb{N} and let GG be a graph. A KtK_t-minor-free graph is a graph that does not contain a KtK_t-minor, and χℓ(G)\chi_\ell(G) denotes its list chromatic number. The 3/23/2-List Hadwiger conjecture. Every KtK_t-minor-free graph GG satisfies

χℓ(G)≤32t.\chi_\ell(G)\le \frac{3}{2}t.

This is the stronger quantitative form of the List Hadwiger conjecture proposed by Kawarabayashi and Mohar and recorded in Seymour's survey. It is open; the paper disproves the earlier stronger possibility with coefficient 11 and proves that any valid coefficient must be at least 2−o(1)2-o(1) asymptotically.

References

Primary source

Raphael Steiner, “Improved lower bound for the list chromatic number of graphs with no K_t minor”, arXiv:2110.09403 (2021).

Additional references

2 papers in this index state this conjecture (2011–2021). The statement above is taken from the most recent of them; the others are 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.