Belavadi–Cameron–Sintiari blowup recolorability conjecture
For every finite prime graph , the following are equivalent: (i) every blowup of is recolorable, meaning that for every integer , the reconfiguration graph of proper -colorings of is connected; (ii) every induced subgraph of is recolorable, meaning that is connected for every integer . Here a blowup of is obtained by replacing each vertex of with a nonempty clique, with two replacement cliques completely adjacent exactly when the corresponding vertices of are adjacent.
References
- Frozen colorings and recolorability of blowups — arXiv — Tianyu Huang, Yulai Ma, Jiaqi Zhang
Source: arXiv
Progress summary
A new preprint claims the conjecture is false in general and completely settles the special case of cycle blowups, but it does not characterize all graphs.
The conjecture asserts that, for a prime graph, all blowups are recolorable exactly when all induced subgraphs are recolorable. Earlier work established substantial positive cases but did not resolve the general question.
Known results
- Every blowup of a -free graph, chordal graph, or prime graph with at most vertices is recolorable.
- Positive results were proved for -free and diamond-free graphs.
- A prime recolorable graph can have a nonrecolorable blowup; the earlier example did not disprove the conjecture because the prime graph contains a nonrecolorable induced .
October 2026 frozen-coloring preprint
Tianyu Huang, Yulai Ma, and Jiaqi Zhang claim that frozen-coloring methods disprove the prime-graph conjecture and give an exact classification of cycle blowups. This is substantive claimed progress, not a full characterization of all graphs, and has not been independently verified in the retrieved sources.
Current status (as of October 2026): The general conjecture remains open; its prime-graph assertion and the cycle-blowup classification are claimed to be settled by a new preprint, but those claims are unverified.
Solutions 0
No solutions have been posted yet.