Abstract
In 1973, Fisk proved that any 4coloring of a 3colorable triangulation of the 2sphere can be obtained from any 3coloring by a sequence of Kempechanges. 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 Kempechange, there exists a 4coloring that cannot be obtained from any 3coloring.
In this paper, we present a lineartime checkable characterization of a 4coloring of a 3colorable triangulation of the 2sphere that can be obtained from a 3coloring by a sequence of recoloring operations at single vertices. In addition, we develop a quadratictime 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 lineartime checkable criterion for a 3colorable triangulation of the 2sphere that all 4colorings can be obtained from a 3coloring by such a sequence. Moreover, we consider a highdimensional setting. As a natural generalization of our first result, we obtain a polynomialtime checkable characterization of a kcoloring of a (k1)colorable triangulation of the (k2)sphere that can be obtained from a (k1)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 (k1)colorable triangulation of the (k2)sphere, one can be obtained from the other by such a sequence is PSPACEcomplete for any fixed k ≥ 4. Our results above can be rephrased as new results on the computational problems named kRecoloring and Connectedness of kColoring Reconfiguration Graph, which are fundamental problems in the field of combinatorial reconfiguration.
BibTeX  Entry
@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43,
author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shunichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta},
title = {{Reconfiguration of Colorings in Triangulations of the Sphere}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {43:143:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17893},
URN = {urn:nbn:de:0030drops178936},
doi = {10.4230/LIPIcs.SoCG.2023.43},
annote = {Keywords: Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration}
}
Keywords: 

Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 