The DP Color Function of Clique-Gluings of Graphs

MaRDI QIDQ6385278zbMATH OpenFDO

Authors Hemanshu Kaul, Michael Maxfield, J. A. Mudrock, Seth Thomason

Publication date 9 December 2021

Mathematics Subject Classification ID

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

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 of a graph $G$, $P(G,m)$, the DP color function of $G$, denoted $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 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)leq(pro{d}_{i=1}^n{P}_{DP}(G_i,m))/left(pro{d}_{i=0}^{p-1}(m-i)ight{)}^{n-1}$ whenever $mgeqp$, where the expression on the right is the DP-coloring analogue of the corresponding chromatic polynomial formula for a $K_p$-gluing of $G_1,ldots,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 $pgeq3$.

This page was built for publication: The DP Color Function of Clique-Gluings of Graphs

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