TOPICS
Search

List Color Function


The list color function P_l(G,m) of a graph G is the minimum number of proper colorings permitted by a list assignment that gives each graph vertex exactly m available colors. If P(G,L) counts the proper colorings selecting the color of each graph vertex from its list L(v), then

 P_l(G,m)=min_(L:|L(v)|=m for all v)P(G,L).

Giving every graph vertex the same list shows that 0<=P_l(G,m)<=P(G,m), where P(G,m) is the chromatic polynomial. The least m for which P_l(G,m)>0 is the choice number.

For every graph G, the list color function equals its chromatic polynomial for all sufficiently large m. Equality for every positive integer m is enumerative chromatic choosability (Allred and Mudrock 2026). For an n-vertex tree, P_l(G,m)=m(m-1)^(n-1). Both counting functions multiply over connected components.


See also

Choice Number, Chromatic Number, Chromatic Polynomial, Enumerative Chromatic Choosability, Proper Coloring

Explore with Wolfram|Alpha

References

Allred, S. and Mudrock, J. A. "Enumerative Chromatic Choosability." Elec. J. Combin. 33, P4.6, 2026. https://doi.org/10.37236/14176.

Cite this as:

Weisstein, Eric W. "List Color Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ListColorFunction.html

Subject classifications