2021/10/10 by Hemanshu Kaul, Kaul, Hemanshu, Jeffrey A. Mudrock +5 · 1 citation
Computer Science · Decision Sciences · #05C15 #05C30 #05C69 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2110.04700
openalex publication_date 2021/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořá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, χDP, of the same. We show that χDP(G \square H) ≤ min\χDP(G) + col(H), χDP(H) + col(G) \ - 1 where col(H) is the coloring number of the graph H. We focus on building tools for lower bound arguments for χDP(G \square H) 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 k ∈ ℕ, what is the smallest t for which χDP(G \square Kk,t)= χDP(G) + k?