{"id":"arxiv/2609.08540","url":"https://arxiv.org/abs/2609.08540","tags":["math.CO"],"score":0,"title":"When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree","domain":"math.CO","source":"arxiv","authors":["Meiqiao Zhang","Fengming Dong"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be a simple graph with maximum degree $Δ\\ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\\ell}(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\\ell}(G,k)=P(G,k)$ for every integer $k\\ge 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\\ge |E(G)|-1$ for graphs with sufficiently many edges relative to their maximum degree.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}