Defective coloring of blowups

Abstract

Given a graph $G$ and an integer $d\ge 0$, its $d$-defective chromatic number $\ddot{I}{‡}^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⊠K_{d+1}$ of a graph $G$ and its ordinary chromatic number, and conjectured that $\ddot{I}‡(G)=\ddot{I}{‡}^d(G⊠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 $\ddot{I}‡(G)\ge \frac{30}{29}\ddot{I}{‡}^d(G⊠K_{d+1})$ for infinitely many $d$. On the positive side, we show that the conjecture holds with a constant factor correction, namely $\ddot{I}{‡}^d(G⊠K_{d+1})\le \ddot{I}‡(G)\le 2\ddot{I}{‡}^d(G⊠K_{d+1})$ for every graph $G$ and $d\ge 0$.