DP‐coloring Cartesian products of graphs

DOI10.1002/JGT.22917zbMATH Open1522.05123arXiv2110.04700MaRDI QIDQ6074580FDOQ6074580

Author name not available (Why is that?), J. A. Mudrock, Author name not available (Why is that?), Hemanshu Kaul

Publication date: 12 October 2023

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

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$?

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)

Cites Work

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

Cited In (4)

• Flexible list colorings: maximizing the number of requests satisfied
• An algebraic approach for counting DP-3-colorings of sparse 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)