{"id":"arxiv/2610.27527","url":"https://arxiv.org/abs/2610.27527","tags":["math.CO"],"score":0,"title":"Frozen colorings and recolorability of blowups","domain":"math.CO","source":"arxiv","authors":["Tianyu Huang","Yulai Ma","Jiaqi Zhang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-20","reactions":{}}