Block symmetries in graph coloring reconfiguration systems (Q6107838)

Reconfiguration systems describe the structure of a set of solutions to a problem with respect to modification rules for incrementally transforming from one solution to another. In this paper, a study of reconfiguration systems for proper coloring of a graph modified by single-vertex recoloring is presented. The structure of the reconfiguration system is captured by the \(k\)-coloring graph \(\mathcal{C}_k(G)\) whose vertex set is the set of all proper \(k\)-colorings of \(G\) and edge set corresponds to proper \(k\)-colorings that differ on a single vertex. Several results on two objects, namely, BC-trees and coloring state complex for capturing of structural properties of graph coloring configuration systems are presented. There is scope for further exploration of the coloring state complex as a graph invariant.