DP‐coloring Cartesian products of graphs

DOI10.1002/JGT.22917MaRDI QIDQ6074580zbMATH OpenFDO

Authors Hemanshu Kaul, J. A. Mudrock

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringCartesian productcorrespondence coloringDP-coloringDP-chromatic numberDP-color function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvov{r}'{a}k and Postle in 2015. Motivated by results related to list coloring Cartesian products of graphs, we initiate the study of the DP-chromatic number, $ch{i}_{DP}$, of the same. We show that $ch{i}_{DP}(GsquareH)leqextminch{i}_{DP}(G)+extcol(H),ch{i}_{DP}(H)+extcol(G)-1$ where $extcol(H)$ is the coloring number of the graph $H$. We focus on building tools for lower bound arguments for $ch{i}_{DP}(GsquareH)$ and use them to show the sharpness of the bound above and its various forms. Our results illustrate that the DP color function of $G$, the DP analogue of the chromatic polynomial, is essential in the study of the DP-chromatic number of the Cartesian product of graphs, including the following question that extends the sharpness problem above and the classical result on gap between list chromatic number and chromatic number: given any graph $G$ and $kinmathbbN$, what is the smallest $t$ for which $ch{i}_{DP}(Gsquare{K}_{k,t})=ch{i}_{DP}(G)+k$?

Recommendations

• A note on the DP-chromatic number of complete bipartite graphs
• On DP-coloring of graphs and multigraphs
• DP-colorings of graphs with high chromatic number
• On the chromatic polynomial and counting DP-colorings of graphs
• Defective DP-colorings of sparse simple graphs

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• A deletion-contraction relation for the DP color function
• 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
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Cover and variable degeneracy
• DP color functions versus chromatic polynomials
• Graph multiplication
• List coloring a Cartesian product with a complete bipartite factor
• List coloring and \(n\)-monophilic graphs.
• List coloring of Cartesian products of graphs
• On the chromatic polynomial and counting DP-colorings of graphs
• On the number of list‐colorings
• Recognizing Cartesian products in linear time
• The DP color function of joins and vertex-gluings of graphs
• The chromatic polynomial and list colorings
• When does the list-coloring function of a graph equal its chromatic polynomial

Cited in

(10)

• Flexible list colorings: maximizing the number of requests satisfied
• A note on fractional DP-coloring of graphs
• Sharp Dirac's theorem for DP-critical graphs
• List coloring of Cartesian products of graphs
• A note on the DP-chromatic number of complete bipartite graphs
• An algebraic approach for counting DP-3-colorings of sparse graphs
• List coloring a Cartesian product with a complete bipartite factor
• The DP color function of joins and vertex-gluings of graphs
• The DP color function of clique-gluings of graphs
• Partial DP-coloring of graphs

This page was built for publication: DP‐coloring Cartesian products of graphs

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