×

Diameter of colorings under Kempe changes. (English) Zbl 1456.05056

Summary: Given a \(k\)-coloring of a graph \(G\), a Kempe-change for two colors \(a\) and \(b\) produces another \(k\)-coloring of \(G\), as follows: first choose a connected component in the subgraph of \(G\) induced by the two color classes of \(a\) and \(b\), and then swap the colors \(a\) and \(b\) in the component. Two \(k\)-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two \(k\)-colorings of a graph \(G\), Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph \(G\) and a positive integer \(k\), Kempe Connectivity asks whether any two \(k\)-colorings of \(G\) are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is \(\mathsf{PSPACE} \)-complete for any fixed \(k \geq 3\), and that it remains \(\mathsf{PSPACE} \)-complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two \(k\)-colorings are Kempe-equivalent.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bonamy, M.; Bousquet, N.; Feghali, C.; Johnson, M., On a conjecture of Mohar concerning Kempe equivalence of regular graphs, J. Comb. Theory, Ser. B, 135, 179-199 (2019) · Zbl 1404.05049
[2] Bonamy, M.; Heinrich, M.; Ito, T.; Kobayashi, Y.; Mizuta, H.; Mühlenthaler, M.; Suzuki, A.; Wasa, K., Diameter of colorings under Kempe changes, (Proc. of COCOON 2019. Proc. of COCOON 2019, LNCS, vol. 11653 (2019)), 52-64 · Zbl 1456.05055
[3] Bonsma, P.; Cereceda, L., Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theor. Comput. Sci., 410, 5215-5226 (2009) · Zbl 1177.05112
[4] Bonsma, P.; Paulusma, D., Using contracted solution graphs for solving reconfiguration problems, (Proc. of MFCS 2016. Proc. of MFCS 2016, LIPIcs, vol. 58 (2016)), Article 20 pp. · Zbl 1398.90188
[5] Cereceda, L.; van den Heuvel, J.; Johnson, M., Finding paths between 3-colorings, J. Graph Theory, 67, 1, 69-82 (2011) · Zbl 1216.05154
[6] Hatanaka, T.; Ito, T.; Zhou, X., The coloring reconfiguration problem on specific graph classes, IEICE Trans. Inf. Syst. E, 102, D(3), 423-429 (2019)
[7] Hearn, R.; Demaine, E., PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, Theor. Comput. Sci., 343, 1-2, 72-96 (2005) · Zbl 1079.68040
[8] van den Heuvel, J., The complexity of change, (Surveys in Combinatorics 2013 (2013)), 127-160 · Zbl 1307.05005
[9] Kempe, A. B., On the geographical problem of the four colours, Am. J. Math., 2, 3, 193-200 (1879)
[10] Las Vergnas, M.; Meyniel, H., Kempe classes and the Hadwiger conjecture, J. Comb. Theory, Ser. B, 31, 1, 95-104 (1981) · Zbl 0471.05028
[11] Melnikov, L. S.; Vizing, V. G., New proof of Brooks’ theorem, J. Comb. Theory, 7, 4, 289-290 (1969) · Zbl 0186.27703
[12] Meyniel, H., Les 5-colorations d’un graphe planaire forment une classe de commutation unique, J. Comb. Theory, Ser. B, 24, 3, 251-257 (1978) · Zbl 0385.05035
[13] Mohar, B., Kempe equivalence of colorings, (Graph Theory in ParisProc. of a Conference in Memory of Claude Berge. Graph Theory in ParisProc. of a Conference in Memory of Claude Berge, Trends in Mathematics (2007)), 287-297 · Zbl 1115.05035
[14] Mohar, B.; Salas, J., A new Kempe invariant and the (non)-ergodicity of the Wang-Swendsen-Koteckỳ algorithm, J. Phys. A, Math. Theor., 42, 22, Article 225204 pp. (2009) · Zbl 1179.37016
[15] Mohar, B.; Salas, J., On the non-ergodicity of the Swendsen-Wang-Koteckỳ algorithm on the Kagomé lattice, J. Stat. Mech. Theory Exp., 2010, 05, Article P05016 pp. (2010) · Zbl 07230217
[16] Mühlenthaler, M.; Wanka, R., The connectedness of clash-free timetables, (Proc. of PATAT 2014 (2014)), 330-346
[17] Mühlenthaler, M., Fairness in Academic Course Timetabling, Lecture Notes in Economics and Mathematical Systems (2015), Springer International Publishing, Dissertation · Zbl 1336.90078
[18] Ravindra, G.; Parthasarathy, K. R., Perfect product graphs, Discrete Math., 20, 177-186 (1977) · Zbl 0371.05028
[19] Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 2, 266-283 (1976) · Zbl 0353.65019
[20] Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci., 4, 177-192 (1970) · Zbl 0188.33502
[21] Vigoda, E., Improved bounds for sampling colorings, J. Math. Phys., 41, 3, 1555-1569 (2000) · Zbl 0978.60083
[22] van der Zanden, T. C., Parameterized complexity of graph constraint logic, (Proc. of IPEC 2015. Proc. of IPEC 2015, LIPIcs, vol. 43 (2015)), 282-293 · Zbl 1378.68097
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.