Id: arxiv/2602.13037 Url: https://arxiv.org/abs/2602.13037 Tags: math.CO, cs.CC Score: 0 Title: Between proper and square coloring of planar graphs, hardness and extremal graphs Domain: math.CO Source: arxiv Authors: Thomas Delépine Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-13 Page: https://delphi.science/r/arxiv/2602.13037 $(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…