Counting List Colorings of Unlabeled Graphs

Abstract

The classic enumerative functions for counting colorings of a graph $G$, such as the chromatic polynomial $P(G,k)$, do so under the assumption that the given graph is labeled. In 1985, Hanlon defined and studied the chromatic polynomial for an unlabeled graph $\mathcal{G}$, $P(\mathcal{G},k)$. Determining $P(\mathcal{G},k)$ amounts to counting colorings under the action of automorphisms of $\mathcal{G}$. In this paper, we consider the problem of counting list colorings of unlabeled graphs. We extend Hanlon's definition to the list context and define the unlabeled list color function, $P_{\ell }(\mathcal{G},k)$, of an unlabeled graph $\mathcal{G}$. In this context, we pursue a fundamental question whose analogues have driven much of the research on counting list colorings and its generalizations: For a given unlabeled graph $\mathcal{G}$, does $P_{\ell }(\mathcal{G},k)=P(\mathcal{G},k)$ when $k$ is large enough? We show the answer to this question is yes for almost all graphs, in particular, for a large class of unlabeled graphs that includes point-determining graphs (also known as twin-free graphs, irreducible graphs, and mating graphs).

arXiv comment14 pages