Defective Coloring of Blowups
The Electronic Journal of Combinatorics · 23.01.2026 · 33 (1)
DOI: 10.37236/14039 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 23.01.2026. Verfasst von Sergey Norin und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Given a graph $G$ and an integer $d\ge 0$, its $d$-defective chromatic number $\chi^d(G)$ is the smallest size of a partition of the vertices into parts inducing subgraphs with maximum degree at most $d$. Guo, Kang and Zwaneveld recently studied the relationship between the $d$-defective chromatic number of the $(d+1)$-fold (clique) blowup $G\boxtimes K_{d+1}$ of a graph $G$ and its ordinary chromatic number, and conjectured that $\chi(G)=\chi^d(G\boxtimes K_{d+1})$ for every graph $G$ and $d\ge 0$. In this note we disprove this conjecture by constructing graphs $G$ of arbitrarily large chromatic number such that $\chi(G)\ge \frac{30}{29}\chi^d(G\boxtimes K_{d+1})$ for infinitely many $d$. On the positive side, we show that the conjecture holds with a constant factor correction, namely $\chi^d(G\boxtimes K_{d+1})\le \chi(G)\le 2\chi^d(G\boxtimes K_{d+1})$ for every graph $G$ and $d\ge 0$.
Zitieren
APA
Norin, S., & Steiner, R. (2026). Defective Coloring of Blowups. The Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/14039
Vancouver
Norin S, Steiner R. Defective Coloring of Blowups. The Electronic Journal of Combinatorics. 2026;33(1). doi:10.37236/14039
BibTeX
@article{Norin2026,
author = {Norin, Sergey and Steiner, Raphael},
title = {Defective Coloring of Blowups},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {1},
doi = {10.37236/14039}
}
EUVIMED