Frozen colorings and recolorability of blowups
The $k$-reconfiguration graph $R_k(G)$ of the proper $k$-colorings of a graph $G$ is the graph whose vertices are the $k$-colorings of $G$, with an edge between two colorings if they differ on exactly one vertex. A graph $G$ is recolorable if $R_k(G)$ is connected for all $k \ge χ(G) + 1$. In this paper, we study recolorability under blowups through frozen colorings, here blowup means replacing vertices with non-empty cliques. We characterize frozen colorings of a blowup of $G$ in terms of maximal independent sets of the base graph, and develop a lifting principle that transfers suitable…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.27527
curl -X POST /api/v1/records/arxiv/2610.27527/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.27527/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'