The DP Color Function of Clique-Gluings of Graphs

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 Dvořák and Postle in 2015. As the analogue of the chromatic polynomial of a graph $G$, $P(G,m)$, the DP color function of $G$, denoted by $P_{DP}(G,m)$, counts the minimum number of DP-colorings over all possible $m$-fold covers. Formulas for chromatic polynomials of clique-gluings of graphs, a fundamental graph operation, are well-known, but the effect of such gluings on the DP color function is not well understood. In this paper we study the DP color function of $K_p$-gluings of graphs. Recently, Becker et. al. asked whether $P_{DP}(G,m)\le ({\prod }_{i=1}^n{P}_{DP}(G_i,m))/{\left({\prod }_{i=0}^{p-1}(m-i)\right)}^{n-1}$ whenever $m\ge p$, where the expression on the right is the DP-coloring analogue of the corresponding chromatic polynomial formula for a $K_p$-gluing, $G$, of $G_1,\dots ,G_n$. Becker et. al. showed this inequality holds when $p=1$. In this paper we show this inequality holds for edge-gluings ($p=2$). On the other hand, we show it does not hold for triangle-gluings ($p=3$), which also answers a question of Dong and Yang (2021). Finally, we show a relaxed version, based on a class of $m$-fold covers that we conjecture would yield the fewest DP-colorings for a given graph, of the inequality holds when $p\ge 3$.

arXiv comment21 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:2104.12268