Frozen colorings and recolorability of blowups
Abstract
The k-reconfiguration graph Rk(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 Rk(G) is connected for all k ≥ χ(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 frozen obstructions from an induced subgraph to a blowup of the ambient graph. This framework yields several consequences. In particular, we answer negatively a question of Belavadi, Cameron and Sintiari on recoloring via modular decomposition, and disprove their conjecture on blowups of prime graphs. We further determine exactly which cycles have all blowups recolorable: this holds for Cn if and only if n∈{3,4,5,7}. The frozen obstructions arising from the negative cases, together with the lifting principle, imply that if every blowup of a graph G is recolorable, then every induced hole of G has length $4$, $5$, or $7$. Finally, using linear programming duality, we show that every such graph G is fractionally co-strongly perfect.
Related
- Existence of flat blowups at boundary points of anisotropic minimizing hypercurrents
- Projective blowups: a formal and multicentered proof
- A Hajnal-Szemerédi Theorem for Skewed Colorings
- Sampling Line-Graph Colorings with Constant Extra Colors
- Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
BibTeX
@misc{huang2026frozen,
title = {{Frozen colorings and recolorability of blowups}},
author = {Tianyu Huang and Yulai Ma and Jiaqi Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27527},
eprint = {2610.27527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27527},
}
RIS
TY - UNPB
TI - Frozen colorings and recolorability of blowups
AU - Tianyu Huang
AU - Yulai Ma
AU - Jiaqi Zhang
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27527
UR - https://arxiv.org/abs/2610.27527
AB - 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 ≥ χ(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 frozen obstructions from an induced subgraph to a blowup of the ambient graph. This framework yields several consequences. In particular, we answer negatively a question of Belavadi, Cameron and Sintiari on recoloring via modular decomposition, and disprove their conjecture on blowups of prime graphs. We further determine exactly which cycles have all blowups recolorable: this holds for C_n if and only if n∈{3,4,5,7}. The frozen obstructions arising from the negative cases, together with the lifting principle, imply that if every blowup of a graph G is recolorable, then every induced hole of G has length $4$, $5$, or $7$. Finally, using linear programming duality, we show that every such graph G is fractionally co-strongly perfect.
ER -