The choice number, or list chromatic number, of a finite simple graph 
is the least nonnegative
integer 
such that every assignment of a list of 
colors to each graph vertex
permits a proper coloring that chooses the color
of each graph vertex from its list.
The related partial list coloring conjecture concerned how many vertices can be properly colored when the lists are shorter than the choice number.
For an integer 
, Gu and Xu (2026, pp. 1-2) proved that finite simple graphs having no complete
graph 
as a graph minor have choice number 
. For such a graph on 
vertices,
they also obtained the bound 
where 
denotes big-O notation and
is the natural
logarithm. Gu and Xu (2026) credit ChatGPT with discovering a key proposition
and report using it for parameter choices and proof revisions.
The authors checked the arguments and take responsibility for them.
The list color function counts the minimum number of allowed proper colorings over all list assignments of a fixed size. Equality of this function with the chromatic polynomial for every positive integer list size is enumerative chromatic choosability, a stronger condition than equality of choice number and chromatic number.
For a random graph 
sampled from 
with 
, Wang and Zeng (2026) proved that its choice number
is asymptotic to its chromatic
number,
 |
with high probability. This includes probabilities 
tending to 1. Wang and Zeng (2026) attribute
the uniform independent set argument to an AI-generated
proof and report AI assistance with the dense case.
The Alon-Krivelevich conjecture predicted an upper bound 
for bipartite graphs
of maximum vertex degree 
. Yu and Yu (2026) construct counterexamples
satisfying
 |
The construction and proof were found with AI assistance and checked by the authors.
The strong fractional choice number instead requires list coloring with several colors selected at each graph vertex (Li and Zhu 2020).
-Minor-Free Graphs." 1 Oct 2026.