Frozen colorings and recolorability of blowups

Source abstract

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 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\in\{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.