License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.43
URN: urn:nbn:de:0030-drops-178936
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17893/
Go to the corresponding LIPIcs Volume Portal


Ito, Takehiro ; Iwamasa, Yuni ; Kobayashi, Yusuke ; Maezawa, Shun-ichi ; Nozaki, Yuta ; Okamoto, Yoshio ; Ozeki, Kenta

Reconfiguration of Colorings in Triangulations of the Sphere

pdf-format:
LIPIcs-SoCG-2023-43.pdf (1 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43,
  author =	{Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shun-ichi 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:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17893},
  URN =		{urn:nbn:de:0030-drops-178936},
  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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI