Between proper and square colorings of planar graphs with maximum degree at most four
An $i$-independent set is a vertex set whose pairwise distance is at least $i+1$. A proper (square) $k$-coloring of a graph $G$ is a partition of its vertex set into $k$ independent ($2$-independent) sets. A packing $(1^{j}, 2^k)$-coloring of a graph $G$ is a partition of $V(G)$ into $j$ independent sets and $k$ $2$-independent sets. It can be viewed as intermediate colorings between proper and square coloring. Wegner conjectured in 1977 that every planar graph with maximum degree at most four is square $9$-colorable. Bousquet, Deschamps, de Meyer, and Pierron proved an upper bound of $12$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.01126
curl -X POST /api/v1/records/arxiv/2604.01126/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.01126/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'