Characterizing multigraphs for which the deletion–contraction bounds on the DP color function and its dual are exact

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle. Its counting analogue of the chromatic polynomial, the DP color function $P_{DP}(G,m)$, minimizes the number of DP-colorings over all full $m$-fold covers of a multigraph $G$, while the dual DP color function $P^*_{DP}(G,m)$ maximizes the same quantity. Mudrock (2022) proved a deletion–contraction relation: $P_{DP}(G-e,m)-P^*_{DP}(G\cdot e,m)\le P_{DP}(G,m)$ for every edge $e$, and $P^*_{DP}(G,m)\le P^*_{DP}(G-e,m)-P_{DP}(G\cdot e,m)$ whenever $e$ is the unique edge between its endpoints. These bounds are exact for trees, simple unicyclic graphs, a parallel-edge even-cycle family, and (for the dual bound) two odd cycles sharing an edge, but no converse is known: the paper poses (Questions 4 and 5) the problem of characterizing the multigraphs for which some edge makes the respective bound an equality for infinitely many $m$.

Background

The chromatic polynomial $P(G,m)$ of a graph $G$ counts the proper vertex colorings of $G$ with colors from $\{1,\dots,m\}$ (colorings in which adjacent vertices receive different colors). A classical tool for computing it, dating to 1940, is the deletion–contraction formula: for any edge $e$ of a simple graph $G$, $P(G,m)=P(G-e,m)-P(G\cdot e,m),$ where $G-e$ is obtained from $G$ by deleting $e$ and $G\cdot e$ by contracting $e$ (identifying its two endpoints). This recursion, combined with induction, determines $P(G,m)$ for many graph families.

List coloring replaces the common palette by per-vertex lists, and its counting analogue, the list color function $P_\ell(G,m)$, is the minimum number of proper list colorings over all assignments of $m$-element lists to the vertices. DP-coloring (also called correspondence coloring), introduced by Dvořák and Postle in 2015, generalizes list coloring one step further: each vertex still receives $m$ colors, but the identification of which color names correspond across an edge may vary from edge to edge. Formally, a cover of a multigraph $G$ is a triple $\mathcal{H}=(L,H,M)$ in which $L$ assigns each vertex $v$ a finite set $L(v)$ (its list), $H$ is a multigraph on the union of all lists whose restriction to each $L(v)$ is a complete graph, and $M$ assigns each edge $e=uv$ of $G$ a matching between $L(u)$ and $L(v)$, the matchings of distinct edges being pairwise disjoint. An $\mathcal{H}$-coloring of $G$ is an independent set of $H$ that meets each list exactly once. The cover is $m$-fold if every list has size $m$, and full if for all distinct vertices $u,v$ the number of edges of $H$ between $L(u)$ and $L(v)$ equals $e_G(u,v)\,m$, where $e_G(u,v)$ denotes the number of edges of $G$ joining $u$ and $v$. A cover has a canonical labeling if the lists can be named $L(v)=\{(v,1),\dots,(v,m)\}$ so that across each edge exactly the pairs $(u,j)$ and $(v,j)$ are matched; then $\mathcal{H}$-colorings are in bijection with proper $m$-colorings.

Kaul and Mudrock (2019) introduced the DP color function $P_{DP}(G,m)$, the minimum number of $\mathcal{H}$-colorings of $G$ over all $m$-fold covers $\mathcal{H}$; the source paper extended the definition to multigraphs by minimizing over full $m$-fold covers. One always has $P_{DP}(G,m)\le P_\ell(G,m)\le P(G,m)$, and the composite inequality can be strict for all sufficiently large $m$: Dong and Yang, generalizing a result of Kaul and Mudrock, showed that if $G$ is a simple graph containing an edge $e$ such that the length of a shortest cycle containing $e$ is even, then $P_{DP}(G,m)<P(G,m)$ for all sufficiently large $m$. So the DP color function genuinely differs from the chromatic polynomial. To state a deletion–contraction relation one must also count maximally, so the source paper introduced the dual DP color function $P^*_{DP}(G,m)$, the maximum number of $\mathcal{H}$-colorings of $G$ over all full $m$-fold covers. Then $P_{DP}(G,m)\le P_\ell(G,m)\le P(G,m)\le P^*_{DP}(G,m)$, and $P^*_{DP}(G,m)$ depends only on the underlying simple graph of $G$.

The source paper (Mudrock, Graphs and Combinatorics 2022) proved the deletion–contraction relation for these functions: for any multigraph $G$, full $m$-fold cover $\mathcal{H}$, and edge $e$, with $\mathcal{H}-e$ and $\mathcal{H}\cdot e$ the canonically induced covers of $G-e$ and $G\cdot e$, $P_{DP}(G,\mathcal{H})\ge P_{DP}(G-e,\mathcal{H}-e)-P_{DP}(G\cdot e,\mathcal{H}\cdot e).$ Consequently, for every $m$, $P_{DP}(G-e,m)-P^*_{DP}(G\cdot e,m)\le P_{DP}(G,m),$ a general lower bound on the DP color function; and when $e_G(u,v)=1$ (no edge parallel to $e$), $P^*_{DP}(G,m)\le P^*_{DP}(G-e,m)-P_{DP}(G\cdot e,m).$ Unlike the chromatic polynomial these recursions are inequalities in general, and their exactness is a structural property of the graph. The paper proves them exact for trees; for simple unicyclic graphs (connected graphs containing exactly one cycle) with $e$ on the cycle; for unicyclic multigraphs whose unique cycle is a 2-cycle, with $e$ on that 2-cycle; for the family of multigraphs whose underlying graph is an even cycle $C_{2k+2}$ with all $l$ parallel edges concentrated between one pair of adjacent vertices (equality for every $m\ge l+1$); and, for the dual upper bound, for graphs formed by two odd cycles sharing exactly one edge. What is missing is the converse direction: a characterization of the multigraphs for which exactness occurs at all.

Problem Statement

The problem is to characterize the exactness cases of the deletion–contraction bounds of Mudrock (2022) — that is, to solve the following two questions posed in that paper (Questions 4 and 5 there). The two questions share one scientific objective: determine for which multigraphs the deletion–contraction recursion for the DP color function and its dual is exact rather than strict, so that recursive deletion–contraction computation of $P_{DP}$ and $P^*_{DP}$ becomes possible precisely for those graphs.

Question 4. For which multigraphs $G$ does there exist an edge $e\in E(G)$ such that $P_{DP}(G-e,m)-P^*_{DP}(G\cdot e,m)=P_{DP}(G,m)$ for infinitely many $m\in\mathbb{N}$?

Question 5. For which multigraphs $G$ does there exist an edge $e$ with endpoints $u$ and $v$ such that $e_G(u,v)=1$ and $P^*_{DP}(G,m)=P^*_{DP}(G-e,m)-P_{DP}(G\cdot e,m)$ for infinitely many $m\in\mathbb{N}$?

A complete answer is a structural characterization of the multigraphs in each question, with proofs of both inclusions (every multigraph in the characterized class admits a witness edge realizing the displayed identity for infinitely many $m$, and no multigraph outside the class does). The characterization must in particular account for the families already known to be exact — trees; simple unicyclic graphs with the edge on the cycle; unicyclic multigraphs containing a 2-cycle with the witness edge on that 2-cycle (for Question 4); the parallel-edge even-cycle family of Proposition 15 of the source (for Question 4); and two odd cycles sharing exactly one edge (for Question 5). The quantifier 'for infinitely many $m$' is part of the statement and must be handled as such, not replaced by 'for all sufficiently large $m$' or 'for some single $m$' unless equivalence is proved.

References

1. Jeffrey A. Mudrock, A Deletion–Contraction Relation for the DP Color Function, Graphs and Combinatorics 38(4), article 115 (2022), DOI 10.1007/s00373-022-02520-z; preprint arXiv:2107.08154, https://arxiv.org/abs/2107.08154
2. Jeffrey A. Mudrock and Gabriel Sharbel, On polynomial representations of dual DP color functions, Discussiones Mathematicae Graph Theory 46(1):67 (2026), DOI 10.7151/dmgt.2593; preprint arXiv:2407.04807, https://arxiv.org/abs/2407.04807
3. Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma and Anne Ullyot, The DP Color Function of Bipartite Graphs, preprint arXiv:2608.02335 (2026), https://arxiv.org/abs/2608.02335
4. Ziqing Li and Yan Yang, Bounds for DP color function and canonical labelings, Graphs and Combinatorics 40(4), article 65 (2024), DOI 10.1007/s00373-024-02794-5; preprint arXiv:2210.06000, https://arxiv.org/abs/2210.06000
5. Hemanshu Kaul and Jeffrey A. Mudrock, On the chromatic polynomial and counting DP-colorings of graphs, Advances in Applied Mathematics 123, article 102131 (2021), DOI 10.1016/j.aam.2020.102131; preprint arXiv:1904.07697, https://arxiv.org/abs/1904.07697
6. Zdeněk Dvořák and Luke Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, Journal of Combinatorial Theory, Series B 129:38–54 (2018), DOI 10.1016/j.jctb.2017.09.001, https://doi.org/10.1016/j.jctb.2017.09.001
7. Manh Vu Bui, Hemanshu Kaul, Michael Maxfield, Jeffrey A. Mudrock, Paul Shin and Seth Thomason, Non-chromatic-Adherence of the DP Color Function via Generalized Theta Graphs, Graphs and Combinatorics 39(3), article 42 (2023), DOI 10.1007/s00373-023-02633-z; preprint arXiv:2110.04058, https://arxiv.org/abs/2110.04058
8. Fengming Dong and Yan Yang, DP color functions versus chromatic polynomials, Advances in Applied Mathematics 134, article 102301 (2022), DOI 10.1016/j.aam.2021.102301; preprint arXiv:2105.11081, https://arxiv.org/abs/2105.11081