Refined list Hadwiger's conjecture

Let λ\lambda be a multiset of positive integers, let kλk_\lambda be the sum of its elements, and let λ|\lambda| be its number of elements. For a graph GG, define h(λ)h(\lambda) to be the maximum integer tt such that every KtK_t-minor-free graph is λ\lambda-choosable. Refined list Hadwiger's conjecture. There are functions ϕ,ψ:NN\phi,\psi:\mathbb{N}\to\mathbb{N} such that

limnψ(n)=\lim_{n\to\infty}\psi(n)=\infty

and, for any multiset λ\lambda of positive integers, if kλϕ(kλλ)k_\lambda\geqslant\phi(k_\lambda-|\lambda|), then

kλh(λ)ψ(kλλ).k_\lambda-h(\lambda)\geqslant\psi(k_\lambda-|\lambda|).

The quantity kλλk_\lambda-|\lambda| measures the distance between λ\lambda-choosability and ordinary kλk_\lambda-colourability. The conjecture asserts that, once kλk_\lambda is sufficiently large relative to this distance, the gap between kλk_\lambda and h(λ)h(\lambda) must grow without bound. The paper proves this for several families of multisets, but whether it holds for all λ\lambda remains open.

Sources & referencesView supporting material

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