Between proper and square coloring of planar graphs, hardness and extremal graphs

Abstract

$(1^a,2^b)$-coloring is the problem of partitioning the vertex set of a graph into $a$ independent sets and $b$ 2-independent sets. This problem was recently introduced by Choi and Liu. We study the computational complexity and extremal properties of $(1^a,2^b)$-coloring. We prove that this problem is NP-Complete even when restricted to certain classes of planar graphs, and we also investigate the extremal values of $b$ when $a$ is fixed and in some $(a+1)$-colorable classes of graphs. In particular, we prove that $k$-degenerate graphs are $(1^k,2^{O(\sqrt{n})})$-colorable, that triangle-free planar graphs are $(1^2,2^{O(\sqrt{n})})$-colorable and that planar graphs are $(1^3,2^{O(\sqrt{n})})$-colorable. All upper bounds obtained are tight up to a constant factor.