Refined list Hadwiger's conjecture

At least 3 years old · documented by

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 ϕ,ψ:N→N\phi,\psi:\mathbb{N}\to\mathbb{N} such that

lim⁡n→∞ψ(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.

References

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.