On Polynomial Representations of the DP Color Function: Theta Graphs and Their Generalizations

arXiv2012.12897MaRDI QIDQ6356831FDOQ6356831

Charlie Halberg, Hemanshu Kaul, Seth Thomason, Andrew C. Liu, J. A. Mudrock, Paul Shin

Publication date: 22 December 2020

Abstract: DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvov{r}'{a}k and Postle in 2015. As the analogue of the chromatic polynomial $P(G,m)$, the DP color function of a graph $G$, denoted $P_{DP}(G,m)$, counts the minimum number of DP-colorings over all possible $m$-fold covers. It is known that, unlike the list color function $P_{ell}(G,m)$, for any $ggeq3$ there exists a graph $G$ with girth $g$ such that $P_{DP}(G,m)<P(G,m)$ when $m$ is sufficiently large. Thus, two fundamental open questions regarding the DP color function are: (i) for which $G$ does there exist an $NinmathbbN$ such that $P_{DP}(G,m)=P(G,m)$ whenever $mgeqN$, (ii) Given a graph $G$ does there always exist an $NinmathbbN$ and a polynomial $p(m)$ such that $P_{DP}(G,m)=p(m)$ whenever $mgeqN$? In this paper we give exact formulas for the DP color function of a Theta graph based on the parity of its path lengths. This gives an explicit answer, including the formulas for the polynomials that are not the chromatic polynomial, to both the questions above for Theta graphs. We extend this result to Generalized Theta graphs by characterizing the exact parity condition that ensures the DP color function eventually equals the chromatic polynomial. To answer the second question for Generalized Theta graphs, we confirm it for the larger class of graphs with a feedback vertex set of size one.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

This page was built for publication: On Polynomial Representations of the DP Color Function: Theta Graphs and Their Generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356831)