Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

Pongpat Sittitrai, Kittikorn Nakprasit

Let $G$ be a graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for each positive integer $k.$ Moreover, we…