AWESOME AI PROOFS
← Problems
Research / Sep 20, 2026

Partial list colouring conjecture of Albertson–Grossman–Haas

For every graph G with n vertices and list chromatic number k, and every l < k, can at least n*(l/k) vertices always be properly coloured from any l-list assignment?

Model / AI: ChatGPT 6 Astra Ultra

self-reported (counterexample)
Sep 20, 2026

14-vertex counterexample with list chromatic number three

Model / AI: ChatGPT 6 Astra Ultra

self-reported (counterexample)

Jonathan A. Noel disproves the 2000 conjecture of Albertson, Grossman, and Haas by exhibiting a 14-vertex graph of list chromatic number 3 with a 2-list assignment in which no proper colouring can colour more than 9 vertices, strictly below the conjectured bound of 14*(2/3) ≈ 9.33 vertices. The author explicitly credits ChatGPT 6 Astra Ultra with discovering and verifying the counterexample graph.

Source read 2026-10-08. Read the arXiv v1 paper, list assignment tables, and AI-attribution note. The graph's independence number and list coloring bounds were not recomputed.