Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
Abstract
A famous folklore result in list coloring demonstrating that the gap between the list chromatic number and chromatic number of a graph can be arbitrarily large is: χℓ(Kl,t) = 1+l if and only if t ≥ ll. DP-coloring (also called correspondence coloring) is a well-studied generalization of list coloring introduced in 2015. In 2018, Mudrock studied the DP analogue of the aforementioned folklore result. He proved that for l ∈ℕ, if μ(l) is the smallest integer t such that χDP(Kl,t)=1+l, then ⌈ ll/l!⌉ ≤ μ(l) ≤ 1+ll(log(l!)+1)/l!. Recently, Kaul, Mudrock, and Sharma studied a more general version of this problem by studying the smallest t for which χDP(G □ Kl,t) = k + l, where G satisfies certain criticality conditions and G □ Kl,t denotes the Cartesian product of G and Kl,t. In this paper, we introduce a notion we call covering families that gives a new perspective on these DP-coloring questions. In particular, if κ(l) denotes the minimum size of a covering family of [l]l, we show that μ(l)=κ(l). We use this equivalence to prove μ(4)=12 and to obtain new general lower bounds on μ(l). We also prove a general upper bound on the minimum size of covering families which yields an improved general upper bound on μ(l) and gives improvements on known bounds for related DP-coloring questions involving Cartesian products with complete bipartite graphs.
Related
- Majority C-coloring in Cartesian products
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- (2,ℱ)-Avoiding Coloring and B-Coloring under Bipartite Exclusions
- On k-limited domination: complexity and Cartesian products
- Sn-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
BibTeX
@misc{kaul2026covering,
title = {{Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs}},
author = {Hemanshu Kaul and Jeffrey A. Mudrock and Emily A. Psyhogios and Gunjan Sharma and Illia Siutkin and Aparna Upadhyay},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33966},
eprint = {2609.33966},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33966},
}
RIS
TY - UNPB
TI - Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
AU - Hemanshu Kaul
AU - Jeffrey A. Mudrock
AU - Emily A. Psyhogios
AU - Gunjan Sharma
AU - Illia Siutkin
AU - Aparna Upadhyay
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33966
UR - https://arxiv.org/abs/2609.33966
AB - A famous folklore result in list coloring demonstrating that the gap between the list chromatic number and chromatic number of a graph can be arbitrarily large is: χ_ℓ(K_l,t) = 1+l if and only if t ≥ l^l. DP-coloring (also called correspondence coloring) is a well-studied generalization of list coloring introduced in 2015. In 2018, Mudrock studied the DP analogue of the aforementioned folklore result. He proved that for l ∈ℕ, if μ(l) is the smallest integer t such that χ_DP(K_l,t)=1+l, then ⌈ l^l/l!⌉ ≤ μ(l) ≤ 1+l^l(log(l!)+1)/l!. Recently, Kaul, Mudrock, and Sharma studied a more general version of this problem by studying the smallest t for which χ_DP(G □ K_l,t) = k + l, where G satisfies certain criticality conditions and G □ K_l,t denotes the Cartesian product of G and K_l,t. In this paper, we introduce a notion we call covering families that gives a new perspective on these DP-coloring questions. In particular, if κ(l) denotes the minimum size of a covering family of [l]^l, we show that μ(l)=κ(l). We use this equivalence to prove μ(4)=12 and to obtain new general lower bounds on μ(l). We also prove a general upper bound on the minimum size of covering families which yields an improved general upper bound on μ(l) and gives improvements on known bounds for related DP-coloring questions involving Cartesian products with complete bipartite graphs.
ER -