Enumerative Chromatic Choosability
Abstract
Chromatic-choosability is a notion of fundamental importance in list coloring. A graph is chromatic-choosable when its chromatic number is equal to its list chromatic number. In 1990, Kostochka and Sidorenko introduced the list color function of a graph G, denoted Pℓ(G,m), which is the list analogue of the chromatic polynomial of G, P(G,m). It is known that for any graph G there is a positive integer k such that Pℓ(G,m) = P(G,m) whenever m ≥ k. In this paper, we study enumerative chromatic-choosability. A graph G is enumeratively chromatic-choosable when Pℓ(G,m) = P(G,m) whenever m ∈ ℕ. We completely determine the graphs of chromatic number two that are enumeratively chromatic-choosable. We construct examples of graphs that are chromatic-choosable but fail to be enumeratively chromatic-choosable, and finally, we explore a conjecture as to whether for every graph G, there is a p ∈ ℕ such that the join of G and Kp is enumeratively chromatic-choosable. The techniques we use to prove results are diverse and include probabilistic ideas and ideas from DP (or correspondence)-coloring.
Related
- Proper conflict-free choosability of sparse graphs with girth at least seven
- Real enumerative invariants relative to the toric boundary and their refinement
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- Enumerative geometry of conics and double covers on projective complete intersections
BibTeX
@article{allred2026enumerative,
title = {{Enumerative Chromatic Choosability}},
author = {Sarah Allred and Jeffrey Allen Mudrock},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/14176},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p6},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Enumerative Chromatic Choosability
AU - Sarah Allred
AU - Jeffrey Allen Mudrock
PY - 2026
DA - 2026/10/09
JO - The Electronic Journal of Combinatorics
DO - 10.37236/14176
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p6
AB - Chromatic-choosability is a notion of fundamental importance in list coloring. A graph is chromatic-choosable when its chromatic number is equal to its list chromatic number. In 1990, Kostochka and Sidorenko introduced the list color function of a graph G, denoted P_ℓ(G,m), which is the list analogue of the chromatic polynomial of G, P(G,m). It is known that for any graph G there is a positive integer k such that P_ℓ(G,m) = P(G,m) whenever m ≥ k. In this paper, we study enumerative chromatic-choosability. A graph G is enumeratively chromatic-choosable when P_ℓ(G,m) = P(G,m) whenever m ∈ ℕ. We completely determine the graphs of chromatic number two that are enumeratively chromatic-choosable. We construct examples of graphs that are chromatic-choosable but fail to be enumeratively chromatic-choosable, and finally, we explore a conjecture as to whether for every graph G, there is a p ∈ ℕ such that the join of G and K_p is enumeratively chromatic-choosable. The techniques we use to prove results are diverse and include probabilistic ideas and ideas from DP (or correspondence)-coloring.
SN - 1077-8926
ER -