EUVIMEDEUVIMED entdecken
Crossref

On the DP-chromatic number of Cartesian products of critical graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma

Discrete Mathematics · 2026-09 · 349 (9) · 115169

DOI: 10.1016/j.disc.2026.115169 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics, 2026-09. Verfasst von Hemanshu Kaul und 2 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

DP-coloring (also called correspondence coloring) is a well-studied generalization of list coloring introduced by Dvo\v{r}\'{a}k and Postle in 2015. The following sharp bound on the DP-chromatic number of the Cartesian product of graphs $G$ and $H$ is known: $\chi_{DP}(G \square H) \leq \text{min}\{\chi_{DP}(G) + \text{col}(H), \chi_{DP}(H) + \text{col}(G) \} - 1$ where $\chi_{DP}(G)$ is the DP-chromatic number of $G$ and $\text{col}(H)$ is the coloring number of $H$. We seek to understand when $\chi_{DP}(G \square K_{l,t})$ is far from its chromatic number: $\chi(G \square K_{l,t}) = \max \{\chi(G), 2 \}$ in the case that $G$ is a $k$-critical graph with $\chi_{DP}(G)=k$. In particular, we have $\chi_{DP}(G \square K_{l,t}) \leq k + l$, and for fixed $l$ we wish to find the smallest $t$ for which this upper bound is achieved. This can be viewed as an extension of the classic result that the list chromatic number of $K_{l,t}$ is $l+1$ if and only if $t \geq l^l$. Our results illustrate that the DP color function of $G$, the DP analogue of the chromatic polynomial, provides a concept and tool that is useful for making progress on this problem.

Zitieren

APA

Kaul, H., Mudrock, J. A., & Sharma, G. (2026). On the DP-chromatic number of Cartesian products of critical graphs. Discrete Mathematics, 349(9), 115169. https://doi.org/10.1016/j.disc.2026.115169

Vancouver

Kaul H, Mudrock JA, Sharma G. On the DP-chromatic number of Cartesian products of critical graphs. Discrete Mathematics. 2026;349(9):115169. doi:10.1016/j.disc.2026.115169

BibTeX
@article{Kaul2026,
  author = {Kaul, Hemanshu and Mudrock, Jeffrey A. and Sharma, Gunjan},
  title = {On the DP-chromatic number of Cartesian products of critical graphs},
  journal = {Discrete Mathematics},
  year = {2026},
  volume = {349},
  number = {9},
  pages = {115169},
  doi = {10.1016/j.disc.2026.115169}
}
Kostenlos starten →