TOPICS
Search

Partial List Coloring Conjecture


The partial list coloring conjecture asserted that if a graph G on n vertices has choice number k, then every assignment of lists of size 1<=l<k permits a proper coloring of at least nl/k vertices (Albertson et al. 2000). Noel (2026) disproved the conjecture by constructing a 14-vertex graph of choice number 3 with a 2-list assignment from which at most 9 vertices can be properly colored.

Noel (2026) reports that ChatGPT 6 Astra Ultra discovered and fully verified the counterexample, subsequently found the human-checkable proof after persistent prompting but almost no mathematical input from the author. The author fully checked the arguments and assumes responsibility for their correctness.


See also

Choice Number, Graph Coloring, Vertex Coloring

Explore with Wolfram|Alpha

References

Albertson, M. O.; Grossman, S.; and Haas, R. "Partial List Colorings." Disc. Math. 214, 235-240, 2000.Noel, J. A. "The Partial List Colouring Conjecture Is False." 20 Sep 2026. https://arxiv.org/abs/2609.23291.

Cite this as:

Weisstein, Eric W. "Partial List Coloring Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PartialListColoringConjecture.html

Subject classifications