Reconfiguration of colorings in triangulations of the sphere
share
In 1973, Fisk proved that any 4-coloring of a 3-colorable triangulation of the 2-sphere can be obtained from any 3-coloring by a sequence of Kempe-changes. On the other hand, in the case where we are only allowed to recolor a single vertex in each step, which is a special case of a Kempe-change, there exists a 4-coloring that cannot be obtained from any 3-coloring. In this paper, we present a characterization of a 4-coloring of a 3-colorable triangulation of the 2-sphere that can be obtained from a 3-coloring by a sequence of recoloring operations at single vertices, and a criterion for a 3-colorable triangulation of the 2-sphere that all 4-colorings can be obtained from a 3-coloring by such a sequence. Moreover, our first result can be generalized to a high-dimensional case, in which “4-coloring,” “3-colorable,” and “2-sphere” above are replaced with “k-coloring,” “(k-1)-colorable,” and “(k-2)-sphere” for k ≥ 4, respectively. In addition, we show that the problem of deciding whether, for given two (k+1)-colorings, one can be obtained from the other by such a sequence is PSPACE-complete for any fixed k ≥ 4. Our results above can be rephrased as new results on the computational problems named k-Recoloring and Connectedness of k-Coloring Reconfiguration Graph, which are fundamental problems in the field of combinatorial reconfiguration.
READ FULL TEXT