Blowup recolorability conjecture for prime graphs
Blowup recolorability conjecture for prime graphs
Let be a prime graph, meaning that has no nontrivial module. A blowup of is obtained by replacing each vertex of 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 is recolorable if and only if every induced subgraph of 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.