Blowup recolorability conjecture for prime graphs

Let GG be a prime graph, meaning that GG has no nontrivial module. A blowup of GG is obtained by replacing each vertex of GG with a nonempty independent set and each edge with all edges between the corresponding sets. A graph is recolorable if its recoloring graph is connected.

Blowup recolorability conjecture. Every blowup of GG is recolorable if and only if every induced subgraph of GG is recolorable.

This conjecture would characterize when all blowups of a prime graph are recolorable in terms of the recolorability of its induced subgraphs. The paper notes that the analogous reduction to blowups is relevant to the question of whether recolorability of all prime graphs in a graph class implies recolorability of every graph in the class, and gives examples showing that a recolorable prime graph can have a non-recolorable blowup.

Sources & referencesView supporting material

Primary source

Manoj Belavadi, Kathie Cameron and Ni Luh Dewi Sintiari, “Recoloring via modular decomposition”, arXiv:2405.06446 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.