← All problems

Belavadi–Cameron–Sintiari blowup recolorability conjecture

For every finite prime graph GG, the following are equivalent: (i) every blowup HH of GG is recolorable, meaning that for every integer k≥χ(H)+1k\geq \chi(H)+1, the reconfiguration graph Rk(H)R_k(H) of proper kk-colorings of HH is connected; (ii) every induced subgraph JJ of GG is recolorable, meaning that Rk(J)R_k(J) is connected for every integer k≥χ(J)+1k\geq \chi(J)+1. Here a blowup of GG is obtained by replacing each vertex of GG with a nonempty clique, with two replacement cliques completely adjacent exactly when the corresponding vertices of GG are adjacent.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 3K13K_1-free graph, chordal graph, or prime graph with at most 55 vertices is recolorable.
  • Positive results were proved for 2K22K_2-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 C6C_6.

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.

Sources

Solutions 0

No solutions have been posted yet.