Hemanshu Kaul, Jeffrey A. Mudrock, Armin Straub — Preprint — 2026
Abstract
Given a graph \(G\), its chromatic polynomial \(P (G, k)\) counts proper \(k\)-colorings, while the corresponding list color function \(P_{\ell} (G, k)\) counts the minimum number of proper colorings across all assignments of \(k\) colors to each vertex. While, obviously, \(P_{\ell} (G, k) \leq P (G, k)\), Donner showed that \(P_{\ell} (G, k) = P (G, k)\) whenever \(k\) is large enough. 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 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 provocative 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.Download
| Link | Size | Description | Hits |
|---|---|---|---|
| unlabeled-list-coloring.pdf | 295.36 KB | Preprint (PDF, 11 pages) | 10 |
BibTeX
@article{unlabeled-list-coloring-2026,
author = {Hemanshu Kaul and Jeffrey A. Mudrock and Armin Straub},
title = {The unlabeled list color function of disconnected graphs},
journal = {Preprint},
year = {2026},
}