AI Proof WatchKeep up with AI contributions

List-chromatic bounds in terms of clique-minor order

Is the list chromatic number of every finite nonempty simple graph at most C times its largest clique-minor order h(G), for one absolute integer C?

Why it matters and what counts as progress

Why it matters: It asks whether the logarithmic loss in general list-colouring bounds can be removed without additional graph restrictions.

What counts as progress: A uniform linear list-colouring bound in clique-minor order, or graph families disproving such a constant-factor bound.

How the problem developed

  1. July 2007 · Partial result [1]

    Ken-ichi Kawarabayashi and Bojan Mohar Proved a relaxed list-colouring form of Hadwiger’s conjecture, allowing bounded monochromatic components in graphs with no Kₖ minor.

  2. 23 Sept 2026 · Linear bound claim [2]

    OpenAI Claimed a universal linear bound on list chromatic number in terms of the Hadwiger number. The result concerns list colouring and does not prove Hadwiger’s ordinary colouring conjecture.

  3. 12 Oct 2026 · Proof simplification [3]

    Jie Gu and Yifan Xu Posted a shorter proof of the stated linear list-colouring bound, preserving the theorem’s list-colouring scope.

AI contribution

Sources

  1. Ken-ichi Kawarabayashi and Bojan Mohar, A relaxed Hadwiger’s Conjecture for list colorings
  2. OpenAI, linear list-coloring bound manuscript
  3. Jie Gu and Yifan Xu, A simpler proof of a linear list-colouring bound
  4. A linear list-coloring bound in terms of the Hadwiger number
  5. Imported graph theorems and assumptions
  6. Lean solution module for the claimed bound
  7. Lean Comparator challenge configuration
  8. OpenAI Math release provenance
Website timeline

Publication dates and editorial changes.