{"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","summary":"$(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}