2026-07-26T01:27:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17893 2024-03-06T11:00:38Z ddc:004 open_access

Reconfiguration of Colorings in Triangulations of the Sphere Ito, Takehiro Iwamasa, Yuni Kobayashi, Yusuke Maezawa, Shun-ichi Nozaki, Yuta Okamoto, Yoshio Ozeki, Kenta Graph coloring Triangulation of the sphere Combinatorial reconfiguration 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 linear-time checkable 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. In addition, we develop a quadratic-time algorithm to find such a recoloring sequence if it exists; our proof implies that we can always obtain a quadratic length recoloring sequence. We also present a linear-time checkable 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, we consider a high-dimensional setting. As a natural generalization of our first result, we obtain a polynomial-time checkable characterization of a k-coloring of a (k-1)-colorable triangulation of the (k-2)-sphere that can be obtained from a (k-1)-coloring by a sequence of recoloring operations at single vertices and the corresponding algorithmic result. Furthermore, we show that the problem of deciding whether, for given two (k+1)-colorings of a (k-1)-colorable triangulation of the (k-2)-sphere, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takehiro Ito and Yuni Iwamasa and Yusuke Kobayashi and Shun-ichi Maezawa and Yuta Nozaki and Yoshio Okamoto and Kenta Ozeki 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.43 urn:nbn:de:0030-drops-178936 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode