Cones of Theta Graphs are Enumeratively Chromatic-Choosable
Abstract
Chromatic choosability is a fundamental notion in list coloring. A graph G is chromatic-choosable if its chromatic number χ(G) equals its list chromatic number χℓ(G). In 1990, Kostochka and Sidorenko introduced the list color function of a graph G, denoted by Pℓ(G,m), which is the list-coloring analogue of its chromatic polynomial P(G,m). A graph G is enumeratively chromatic-choosable if Pℓ(G,m)=P(G,m) for every m ∈ ℕ. In 2002, Ohba proved that for every graph G, there exists an N ∈ ℕ such that Kp ∨ G is chromatic-choosable whenever p ≥ N. Allred and Mudrock recently conjectured that an analogous statement holds for enumerative chromatic choosability. In this paper, we prove that K1 ∨ G is enumeratively chromatic-choosable whenever G is a theta graph. Our proof combines classical inequalities, the polynomial method, and ideas from DP (or correspondence) coloring.
Related
BibTeX
@misc{barnes2026cones,
title = {{Cones of Theta Graphs are Enumeratively Chromatic-Choosable}},
author = {Kingston Barnes and Vincent Fesenmeier and Braxton Gaither and Michael Guthrie and Leonardo Marciaga and Lucas Miller and Fennec Morrissette and Jeffrey A. Mudrock and Gavin Nguyen and Rose Zellner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15132},
eprint = {2610.15132},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15132},
}
RIS
TY - UNPB
TI - Cones of Theta Graphs are Enumeratively Chromatic-Choosable
AU - Kingston Barnes
AU - Vincent Fesenmeier
AU - Braxton Gaither
AU - Michael Guthrie
AU - Leonardo Marciaga
AU - Lucas Miller
AU - Fennec Morrissette
AU - Jeffrey A. Mudrock
AU - Gavin Nguyen
AU - Rose Zellner
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15132
UR - https://arxiv.org/abs/2610.15132
AB - Chromatic choosability is a fundamental notion in list coloring. A graph G is chromatic-choosable if its chromatic number χ(G) equals its list chromatic number χ_ℓ(G). In 1990, Kostochka and Sidorenko introduced the list color function of a graph G, denoted by P_ℓ(G,m), which is the list-coloring analogue of its chromatic polynomial P(G,m). A graph G is enumeratively chromatic-choosable if P_ℓ(G,m)=P(G,m) for every m ∈ ℕ. In 2002, Ohba proved that for every graph G, there exists an N ∈ ℕ such that K_p ∨ G is chromatic-choosable whenever p ≥ N. Allred and Mudrock recently conjectured that an analogous statement holds for enumerative chromatic choosability. In this paper, we prove that K_1 ∨ G is enumeratively chromatic-choosable whenever G is a theta graph. Our proof combines classical inequalities, the polynomial method, and ideas from DP (or correspondence) coloring.
ER -