PreprintarXiv licencearXiv
When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
Abstract
Let G be a simple graph with maximum degree Δ≥ 3, and let P(G,k) denote its chromatic polynomial. For each positive integer k, the list-color function Pℓ(G,k) is the minimum number of L-colorings of G over all k-assignments L. In this paper, we prove that Pℓ(G,k)=P(G,k) for every integer k≥ 23.41Δ. This gives a threshold for equality that is linear in the maximum degree and independent of the number of vertices or edges. It improves the known sufficient condition k≥ |E(G)|−1 for graphs with sufficiently many edges relative to their maximum degree.
Related
- A total variation threshold for the first coordinates of uniform parking functions via Lorentzian polynomials
- Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs
- Bounds on the maximum denominator of fractional chromatic numbers
- Defective chromatic polynomials
- The rich-neighbor chromatic index is linear in the maximum degree
BibTeX
@misc{zhang2026when,
title = {{When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree}},
author = {Meiqiao Zhang and Fengming Dong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08540},
eprint = {2609.08540},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08540},
}
RIS
TY - UNPB
TI - When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
AU - Meiqiao Zhang
AU - Fengming Dong
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.08540
UR - https://arxiv.org/abs/2609.08540
AB - Let G be a simple graph with maximum degree Δ≥ 3, and let P(G,k) denote its chromatic polynomial. For each positive integer k, the list-color function P_ℓ(G,k) is the minimum number of L-colorings of G over all k-assignments L. In this paper, we prove that P_ℓ(G,k)=P(G,k) for every integer k≥ 23.41Δ. This gives a threshold for equality that is linear in the maximum degree and independent of the number of vertices or edges. It improves the known sufficient condition k≥ |E(G)|−1 for graphs with sufficiently many edges relative to their maximum degree.
ER -