A deletion-contraction relation for the DP color function

DOI10.1007/S00373-022-02520-ZMaRDI QIDQ2156187zbMATH OpenOpenAlexFDO

Authors J. A. Mudrock

Publication date 18 July 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.08154

zbMATH Keywords

chromatic polynomialDP color functionDP-coloringgraph coloringlist coloring

Mathematics Subject Classification ID

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

Abstract: DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvov{r}'{a}k and Postle. The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$. A well-known tool for computing the chromatic polynomial of graph $G$ is the deletion-contraction formula which relates $P(G,m)$ to the chromatic polynomials of two smaller graphs. The DP color function of a graph $G$, denoted $P_{DP}(G,m)$, is a DP-coloring analogue of the chromatic polynomial, and $P_{DP}(G,m)$ is the minimum number of DP-colorings of $G$ over all possible $m$-fold covers. In this paper we present a deletion-contraction relation for the DP color function. To make this possible, we extend the definition of the DP color function to multigraphs. We also introduce the dual DP color function of a graph $G$, denoted $P_{DP}^{\ast }(G,m)$, which counts the maximum number of DP-colorings of $G$ over certain $m$-fold covers. We show how the dual DP color function along with our deletion-contraction relation yields a new general lower bound on the DP color function of a graph.

Recommendations

• On the chromatic polynomial and counting DP-colorings of graphs
• DP color functions versus chromatic polynomials
• Answers to two questions on the DP color function
• Non-chromatic-adherence of the DP color function via generalized theta graphs
• The DP color function of joins and vertex-gluings of graphs

Cites work

• A note on a Brooks' type theorem for DP-coloring
• A note on the DP-chromatic number of complete bipartite graphs
• Answers to two questions on the DP color function
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• DP-3-coloring of some planar graphs
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• List coloring and n-monophilic graphs.
• On DP-coloring of graphs and multigraphs
• On the chromatic polynomial and counting DP-colorings of graphs
• On the number of list‐colorings
• Sharp Dirac's theorem for DP-critical graphs
• The chromatic polynomial and list colorings
• The dissection of rectangles into squares
• The Johansson-Molloy theorem for DP-coloring
• When does the list-coloring function of a graph equal its chromatic polynomial

Cited in

(7)

• Answers to two questions on the DP color function
• Non-chromatic-adherence of the DP color function via generalized theta graphs
• DP‐coloring Cartesian products of graphs
• An algebraic approach for counting DP-3-colorings of sparse graphs
• On polynomial representations of the DP color function: theta graphs and their generalizations
• The DP color function of clique-gluings of graphs
• On polynomial representations of dual DP color functions

This page was built for publication: A deletion-contraction relation for the DP color function

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