{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihmvhi3absq7m5qbgasfvpxdrehzsb3bzbfvapmk3vhm6i4wo25vi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mexfdr2lazi2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.13037v1",
  "publishedAt": "2026-02-16T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Thomas Delépine"
  ],
  "textContent": "**Authors:** Thomas Delépine\n\n$(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.",
  "title": "Between proper and square coloring of planar graphs, hardness and extremal graphs"
}