Document Open Access Logo

Reconfiguration of Colorings in Triangulations of the Sphere

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.43.pdf
  • Filesize: 1.13 MB
  • 16 pages

Document Identifiers

Author Details

Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yuni Iwamasa
  • Graduate School of Informatics, Kyoto University, Japan
Yusuke Kobayashi
  • Research Institute for Mathematical Sciences, Kyoto University, Japan
Shun-ichi Maezawa
  • Department of Mathematics, Tokyo University of Science, Japan
Yuta Nozaki
  • Faculty of Environment and Information Sciences, Yokohama National University, Japan
  • SKCM², Hiroshima University, Japan
Yoshio Okamoto
  • Graduate School of Informatics and Engineering, The University of Electro-Communications, Tokyo, Japan
Kenta Ozeki
  • Faculty of Environment and Information Sciences, Yokohama National University, Japan

Funding

  • Ito, Takehiro: JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814, JP20H05793.
  • Iwamasa, Yuni: JSPS KAKENHI Grant Numbers JP20H05795, JP20K23323, JP22K17854.
  • Kobayashi, Yusuke: JSPS KAKENHI Grant Numbers JP20H05795.
  • Maezawa, Shun-ichi: JSPS KAKENHI Grant Numbers JP20H05795, JP22K13956.
  • Nozaki, Yuta: JSPS KAKENHI Grant Numbers JP20H05795, JP20K14317.
  • Okamoto, Yoshio: JSPS KAKENHI Grant Numbers JP20H05795, JP20K11670.
  • Ozeki, Kenta: JSPS KAKENHI Grant Numbers JP20H05795, JP22K19773.

Acknowledgements

We thank Naonori Kakimura and Naoyuki Kamiyama for related discussion, and anonymous reviewers for helpful suggestions.

Cite AsGet BibTex

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of Colorings in Triangulations of the Sphere. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.43

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph coloring
Keywords
  • Graph coloring
  • Triangulation of the sphere
  • Combinatorial reconfiguration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marthe Bonamy, Nicolas Bousquet, Carl Feghali, and Matthew Johnson. On a conjecture of Mohar concerning Kempe equivalence of regular graphs. J. Combin. Theory, Ser. B, 135:179-199, 2019. URL: https://doi.org/10.1016/j.jctb.2018.08.002.
  2. Marthe Bonamy, Vincent Delecroix, and Clement Legrand–Duchesne. Kempe changes in degenerate graphs. arXiv e-prints, 2021. URL: https://doi.org/10.48550/arXiv.2112.02313.
  3. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci., 410(50):5215-5226, 2009. URL: https://doi.org/10.1016/j.tcs.2009.08.023.
  4. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Connectedness of the graph of vertex-colourings. Discrete Math., 308:913-919, 2008. URL: https://doi.org/10.1016/j.disc.2007.07.028.
  5. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Mixing 3-colourings in bipartite graphs. Europ. J. Combin., 30:1593-1606, 2009. URL: https://doi.org/10.1016/j.ejc.2009.03.011.
  6. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Finding paths between 3-colourings. J. Graph Theory, 67:69-82, 2011. URL: https://doi.org/10.1002/jgt.20514.
  7. Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings via linear programming. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2216-2234. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.134.
  8. A.V. Chernavsky and V.P. Leksine. Unrecognizability of manifolds. Annals of Pure and Applied Logic, 141(3):325-335, 2006. URL: https://doi.org/10.1016/j.apal.2005.12.011.
  9. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210-223, 1985. URL: https://doi.org/10.1137/0214017.
  10. Daniel W. Cranston and Landon Rabern. Brooks' theorem and beyond. J. Graph Theory, 80:199-225, 2015. URL: https://doi.org/10.1002/jgt.21847.
  11. William H. Cunningham and Jack Edmonds. A combinatorial decomposition theory. Canadian J. Math., 32(3):734-765, 1980. URL: https://doi.org/10.4153/CJM-1980-057-7.
  12. Carl Feghali. Kempe equivalence of 4-critical planar graphs. arXiv e-prints, 2021. URL: https://doi.org/10.48550/arXiv.2101.04065.
  13. Carl Feghali, Matthew Johnson, and Daniël Paulusma. Kempe equivalence of colourings of cubic graphs. Europ. J. Combin., 59:1-10, 2017. URL: https://doi.org/10.1016/j.ejc.2016.06.008.
  14. Steve Fisk. Combinatorial structure on triangulations. I. The structure of four colorings. Advances in Math., 11:326-338, 1973. URL: https://doi.org/10.1016/0001-8708(73)90015-7.
  15. Steve Fisk. Combinatorial structures on triangulations. II. Local colorings. Advances in Math., 11:339-350, 1973. URL: https://doi.org/10.1016/0001-8708(73)90016-9.
  16. Steve Fisk. Geometric coloring theory. Advances in Math., 24(3):298-340, 1977. URL: https://doi.org/10.1016/0001-8708(77)90061-5.
  17. Thomas P. Hayes, Juan Carlos Vera, and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. Random Struct. Algorithms, 47(4):731-759, 2015. URL: https://doi.org/10.1002/rsa.20560.
  18. Percy J Heawood. On the four-colour map theorem. Quart. J. Pure Appl. Math., 29:270-285, 1898. Google Scholar
  19. Percy John Heawood. Map-colour theorems. Quarterly J. Math., 24:332-338, 1890. Google Scholar
  20. John E. Hopcroft and Robert Endre Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974. URL: https://doi.org/10.1145/321850.321852.
  21. Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of colorings in triangulations of the sphere. arXiv e-prints, 2022. URL: https://doi.org/10.48550/arXiv.2210.17105.
  22. Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, and Takahisa Toda. ZDD-based algorithmic framework for solving shortest reconfiguration problems. arXiv e-prints, 2022. URL: https://doi.org/10.48550/arXiv.2207.13959.
  23. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms, 7(2):157-166, 1995. URL: https://doi.org/10.1002/rsa.3240070205.
  24. Michel Las Vergnas and Henri Meyniel. Kempe classes and the Hadwiger conjecture. J. Combin. Theory, Ser. B, 31:95-104, 1981. URL: https://doi.org/10.1016/S0095-8956(81)80014-7.
  25. Naoki Matsumoto and Atsuhiro Nakamoto. Generating 4-connected even triangulations on the sphere. Discrete Math., 338:64-705, 2015. URL: https://doi.org/10.1016/j.disc.2014.08.017.
  26. Henri Meyniel. Les 5-colorations d'un graphe planaire forment une classe de commutation unique. J. Combin. Theory, Ser. B, 24:251-257, 1978. URL: https://doi.org/10.1016/0095-8956(78)90042-4.
  27. Bojan Mohar. Kempe equivalence of colorings. In Graph theory in Paris, Trends Math., pages 287-297. Birkhäuser, Basel, 2007. URL: https://doi.org/10.1007/978-3-7643-7400-6_22.
  28. Bojan Mohar and Jesús Salas. A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm. J. Phys. A: Math. Theor., 42(22):225204, 2009. URL: https://doi.org/10.1088/1751-8113/42/22/225204.
  29. James R. Munkres. Elements of Algebraic Topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984. Google Scholar
  30. Naomi Nishimura. Introduction to reconfiguration. Algorithms (Basel), 11(4):Paper No. 52, 25, 2018. URL: https://doi.org/10.3390/a11040052.
  31. Joachim H. Rubinstein. An algorithm to recognize the 3-sphere. In S. D. Chatterji, editor, Proceedings of the International Congress of Mathematicians, pages 601-611, Basel, 1995. Birkhäuser Basel. Google Scholar
  32. Thomas L. Saaty. Thirteen colorful variations on Guthrie’s four-color conjecture. American Math. Monthly, 79:1, 1972. URL: https://doi.org/10.2307/2978124.
  33. Saul Schleimer. Sphere recognition lies in NP. In Michael Usher, editor, Low-dimensional and Symplectic Topology, volume 82 of Proceedings of Symposia in Pure Mathematics, pages 183-213, Providence, RI, 2011. American Mathematical Society. Google Scholar
  34. Abigail Thompson. Thin position and the recognition problem for S³. Mathematical Research Letters, 1:613-630, 1994. URL: https://doi.org/10.4310/MRL.1994.v1.n5.a9.
  35. Jan van den Heuvel. The complexity of change. In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 127-160. Cambridge Univ. Press, Cambridge, 2013. Google Scholar
  36. Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000. URL: https://doi.org/10.1063/1.533196.
  37. I. A. Volodin, V. E. Kuznetsov, and A. T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Russian Mathematical Surveys, 29(5):71-172, 1974. URL: https://doi.org/10.1070/RM1974v029n05ABEH001296.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact