The list color function Pℓ(G,m)P_\ell(G,m) of a graph GG is the list-coloring analogue of the chromatic polynomial P(G,m)P(G,m): it is the minimum number of proper colorings of GG over all assignments of lists of mm colors to the vertices. A graph is enumeratively chromatic-choosable when Pℓ(G,m)=P(G,m)P_\ell(G,m)=P(G,m) for every natural number mm. Since a classical theorem of Ohba (sharpened by Noel, Reed, and Wu) shows that every graph becomes chromatic-choosable after taking the join with a sufficiently large complete graph, Allred and Mudrock (2025) conjectured the enumerative analogue: for every graph GG there exists a positive integer pp such that the join G∨KpG\vee K_p is enumeratively chromatic-choosable. The conjecture remains open in full generality, with K1∨Θ(2,2,2k)K_1\vee\Theta(2,2,2k) the main positive evidence and complete multipartite graphs the highlighted untouched test class. The adjacent Kirov–Naimi question of whether the list color function number ν(G)\nu(G) always equals the list color function threshold τ(G)\tau(G), which the source poses alongside this conjecture, also remains open.

Background

A proper coloring of a graph GG assigns colors to vertices so that adjacent vertices receive different colors; the chromatic number χ(G)\chi(G) is the least number of colors needed. In list coloring, each vertex vv is given its own list L(v)L(v) of available colors, and one asks for a proper coloring with f(v)∈L(v)f(v)\in L(v) for every vertex; an mm-assignment gives every vertex a list of size mm. The list chromatic number χℓ(G)\chi_\ell(G) is the least kk such that GG is colorable from every kk-assignment, and GG is called chromatic-choosable when χℓ(G)=χ(G)\chi_\ell(G)=\chi(G).

The chromatic polynomial P(G,m)P(G,m), introduced by Birkhoff in 1912, counts the proper colorings of GG using colors from [m][m]. Kostochka and Sidorenko proposed in 1990 its list analogue: the list color function Pℓ(G,m)P_\ell(G,m) is the minimum, over all mm-assignments LL, of the number of proper colorings of GG from LL. Clearly Pℓ(G,m)≤P(G,m)P_\ell(G,m)\le P(G,m), and the two can differ dramatically for small mm. Donner proved in 1992 that for every graph GG there is a kk with Pℓ(G,m)=P(G,m)P_\ell(G,m)=P(G,m) whenever m≥km\ge k; the best general bound is due to Dong and Zhang (2023): τ(G)≤∣E(G)∣−1\tau(G)\le|E(G)|-1 for graphs with at least four edges. Two invariants track the onset of equality: the list color function number ν(G)\nu(G) is the smallest t≥χ(G)t\ge\chi(G) with Pℓ(G,t)=P(G,t)P_\ell(G,t)=P(G,t), and the list color function threshold τ(G)\tau(G) is the smallest k≥χ(G)k\ge\chi(G) such that equality holds for all m≥km\ge k; always χ(G)≤χℓ(G)≤ν(G)≤τ(G)\chi(G)\le\chi_\ell(G)\le\nu(G)\le\tau(G). A graph is enumeratively chromatic-choosable when τ(G)=χ(G)\tau(G)=\chi(G), i.e. Pℓ(G,m)=P(G,m)P_\ell(G,m)=P(G,m) for all m≥χ(G)m\ge\chi(G) — equivalently for all m∈Nm\in\mathbb{N}, since both counts vanish when m<χ(G)m<\chi(G) — and weakly enumeratively chromatic-choosable when merely ν(G)=χ(G)\nu(G)=\chi(G). The notion was first formally defined by Kaul, Kumar, Liu, Mudrock, Rewers, Shin, Tanahara, and To (2023), though it had been pursued since the early 1990s.

For ordinary chromatic-choosability there is a classical phenomenon of stabilization under joins. The join G∨HG\vee H of disjoint graphs GG and HH is obtained from their union by joining every vertex of GG to every vertex of HH (so χ(G∨Kp)=χ(G)+p\chi(G\vee K_p)=\chi(G)+p). Ohba proved in 2002 that for every graph GG there is an NN such that G∨KpG\vee K_p is chromatic-choosable whenever p≥Np\ge N, and Noel, Reed, and Wu famously proved Ohba's conjecture that every graph with at most 2χ(G)+12\chi(G)+1 vertices is chromatic-choosable.

Allred and Mudrock (2025) began the systematic study of the enumerative analogue. They completely characterized the enumeratively chromatic-choosable graphs of chromatic number two (the connected ones are exactly those whose core — the graph left after repeatedly deleting degree-1 vertices — is K1K_1, an even cycle C2k+2C_{2k+2}, or K2,3K_{2,3}). For the theta graphs Θ(2,2,2k)\Theta(2,2,2k) with k≥2k\ge2 (a theta graph Θ(l1,l2,l3)\Theta(l_1,l_2,l_3) is a pair of end vertices joined by three internally disjoint paths of lengths l1,l2,l3l_1,l_2,l_3; these graphs are 2-choosable by the classical characterization of 2-choosable graphs), they proved equality Pℓ=PP_\ell=P for every m≥3m\ge3 even though these graphs fail to be even weakly enumeratively chromatic-choosable at m=2m=2, extending Thomassen's 2009 example Θ(2,2,4)\Theta(2,2,4). As their main evidence toward the enumerative Ohba phenomenon, they proved that K1∨Θ(2,2,2k)K_1\vee\Theta(2,2,2k) is enumeratively chromatic-choosable for every kk. On the negative side, the complete multipartite graph K2,2,4K_{2,2,4} is chromatic-choosable (by results of Enomoto, Ohba, Ota, and Sakamoto) yet not even weakly enumeratively chromatic-choosable, which is why they single out complete multipartite graphs as the natural, still untouched test class. In this context they posed Conjecture 6.

A key structural difficulty is that a closely related fundamental question remains open: Kirov and Naimi asked (in their language, in terms of nn-monophilic graphs) whether the list color function number always equals the list color function threshold, i.e. whether ν(G)=τ(G)\nu(G)=\tau(G) for every graph GG — equivalently, whether equality Pℓ(G,m)=P(G,m)P_\ell(G,m)=P(G,m) at one point m≥χ(G)m\ge\chi(G) forces equality at m+1m+1. No graph with ν(G)<τ(G)\nu(G)<\tau(G) is known, but no proof of equality exists either; the question remains open. Consequently, verifying enumerative chromatic-choosability requires controlling all m≥χm\ge\chi simultaneously and cannot be reduced to a check at a single value of mm.

Problem Statement

Prove or disprove Conjecture 6 of Allred and Mudrock (2025): for every finite simple graph GG there exists a positive integer pp such that the join G∨KpG\vee K_p is enumeratively chromatic-choosable, that is, Pℓ(G∨Kp, m)=P(G∨Kp, m) for every m∈NP_\ell(G\vee K_p,\,m)=P(G\vee K_p,\,m)\ \text{for every}\ m\in\mathbb{N} (or equivalently, for every m≥χ(G)+pm\ge\chi(G)+p, since both sides vanish for smaller mm).

References

  1. Sarah Allred and Jeffrey A. Mudrock, "Enumerative Chromatic Choosability", arXiv preprint (2025), arXiv:2505.05662, DOI 10.48550/arxiv.2505.05662, https://arxiv.org/abs/2505.05662 (primary source)
  2. Yanghong Chi, Seoju Lee, Fennec Morrissette, Jeffrey Mudrock, Gavin Nguyen, and Benjamin Whatley, "Enumeratively chromatic-choosable theta graphs", Enumerative Combinatorics and Applications 6(3) (2026), DOI 10.54550/eca2026v6s3r23; arXiv:2605.10861, https://arxiv.org/abs/2605.10861
  3. Radoslav Kirov and Ramin Naimi, "List coloring and n-monophilic graphs", Ars Combinatoria 124 (2016) 329–340; arXiv:1004.5183 (2010), https://arxiv.org/abs/1004.5183
  4. Kyoji Ohba, "On chromatic-choosable graphs", Journal of Graph Theory 40(2) (2002) 130–135, DOI 10.1002/jgt.10033, https://doi.org/10.1002/jgt.10033
  5. Jonathan A. Noel, Bruce A. Reed, and Hehui Wu, "A proof of a conjecture of Ohba", Journal of Graph Theory 79(2) (2015) 86–102, DOI 10.1002/jgt.21819, https://doi.org/10.1002/jgt.21819
  6. Hikoe Enomoto, Kyoji Ohba, Katsuhiro Ota, and Junko Sakamoto, "Choice number of some complete multi-partite graphs", Discrete Mathematics 244(1–3) (2002) 55–66, DOI 10.1016/S0012-365X(01)00059-0, https://doi.org/10.1016/S0012-365X(01)00059-0
  7. Carsten Thomassen, "The chromatic polynomial and list colorings", Journal of Combinatorial Theory, Series B 99(2) (2009) 474–479, DOI 10.1016/j.jctb.2008.09.005, https://doi.org/10.1016/j.jctb.2008.09.005
  8. Quentin Donner, "On the number of list-colorings", Journal of Graph Theory 16(3) (1992) 239–245, DOI 10.1002/jgt.3190160307, https://doi.org/10.1002/jgt.3190160307
  9. Fengming Dong and Meiqiao Zhang, "An improved lower bound of P(G,L)−P(G,k) for k-assignments L", Journal of Combinatorial Theory, Series B 161 (2023) 109–119, DOI 10.1016/j.jctb.2023.02.002, https://doi.org/10.1016/j.jctb.2023.02.002
  10. Hemanshu Kaul, Akash Kumar, Andrew Liu, Jeffrey A. Mudrock, Patrick Rewers, Paul Shin, M. S. Tanahara, and K. To, "Bounding the list color function threshold from above", Involve, a Journal of Mathematics 16(5) (2023) 849–882, DOI 10.2140/involve.2023.16.849, https://doi.org/10.2140/involve.2023.16.849
  11. "Problems Proposed at the Problem Session of the Prachatice Conference on Graph Theory" (includes the problem of Kostochka and Sidorenko introducing the list color function), Annals of Discrete Mathematics 51 (1992) 375–384, DOI 10.1016/s0167-5060(08)70659-9, https://doi.org/10.1016/S0167-5060(08)70659-9
  12. Nandana K. Vasudevan, K. Somasundaram, and N. Narayanan, "List-Coloring and Chromatic-Choosability – A Dynamic Survey", arXiv preprint (2026), arXiv:2606.31702, https://arxiv.org/abs/2606.31702