A linear list-coloring bound in terms of the Hadwiger number
We prove that every finite nonempty graph G satisfies $\chi_{\mathrm{list}}(G)\le C h(G)$ for an absolute integer C , where $h(G)$ is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number
curl -X POST /api/v1/records/openai-math/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
A shorter proof of the linear list Hadwiger conjecturearXiv.orgYangyan Gu, Rongxing XuOct 1, 2026in the index
The linear list Hadwiger conjecture asserts that every $K_t$-minor-free graph is $O(t)$-choosable. Following an approach outlined by Delcourt and Postle, we recently established $O(t\log\log t)$-choosability. Soon afterward, OpenAI provided a proof of the conjecture. A key new ingredient of their…