2026/07/18 by Hemanshu Kaul, Jeffrey A. Mudrock, Armin Straub
#math.CO
Given a graph G, its chromatic polynomial P (G, k) counts proper k-colorings, while the corresponding list color function Pℓ (G, k) counts the minimum number of proper colorings across all assignments of k colors to each vertex. While it is clear that Pℓ (G, k) ≤ P (G, k), Donner showed in 1992 that Pℓ (G, k) = P (G, k) whenever k is sufficiently large. In 1985, Hanlon defined and studied the chromatic polynomial for an unlabeled graph. A list version of Hanlon's notion was introduced in 2024 by Kaul and Mudrock, who further raised the question of whether the analog of Donner's result holds in the unlabeled case. While they proved this for all connected point-determining graphs, even the case of the edgeless graph on n vertices remained open and was posed as a conjecture. We prove this conjecture and show that it implies that, more generally, a disconnected graph satisfies the unlabeled analog of Donner's result if all of its connected components do.