2024/09/09 by Hemanshu Kaul, Jeffrey A. Mudrock, Kaul, Hemanshu +1
Computer Science · #05A99 #05C15 #05C30 #20B25 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2409.06063
openalex publication_date 2024/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 G, P(G, k). Determining P(G, k) amounts to counting colorings under the action of automorphisms of 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_ℓ(G, k), of an unlabeled graph 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 G, does P_ℓ(G, k) = P(G, k) when k is large enough? We show the answer to this question is yes for a large class of unlabeled graphs that include point-determining graphs (also known as twin-free graphs, irreducible graphs, and mating graphs).