Given a graph G and a proper vertex coloring of G, a 2-coloring induced subgraph of G is a subgraph induced by all the vertices with one of two colors, a component of a 2-coloring induced subgraph is called a 2-coloring component. To make a Kempe change is to obtain one coloring from another by exchanging the colors of vertices in a 2-coloring component. Two colorings are Kempe equivalent if each one can be obtained from the other by a series of Kempe changes. Mohar conjectured that, for k≥3, all k-colorings of connected k-regular graphs that are not complete are Kempe equivalent. Feghali et al. addressed the case k=3, and it is still an unsolved conjecture for k≥4. This paper considers the case k=4 by showing that: (1) if G is a connected 4-regular graph that is not 3-connected, then all 4-colorings of G are Kempe equivalent; (2) if G is a connected 4-regular graph that contains an induced subgraph isomorphic to a 4-wheel or a nearly complete graph of order 5, then all 4-colorings of G are Kempe equivalent; (3) if G is a 3-connceted 4-regular graph with a 4-coloring f and a vertex x such that there are three or four neighbors of x colored with the same color under f, then all 4-colorings of G are Kempe equivalent.
KEMPE A B. On the geographical problem of the four colors[J]. American Journal of Mathematics, 1879, 2(3): 193-200. doi: 10.2307/2369235.
[2]
MUHLENTHALER M and WANKA R. The connectedness of clash-free timetables[C]. 10th International Conference of the Practice and Theory of Automated Timetabling, York, United Kingdom, 2014: 26-29.
[3]
WANG J S, SWENDSEN R H, and KOTECKY R. Antiferromagnetic potts models[J]. Physical Review Letters, 1989, 63(2): 109-112. doi: 10.1103/PhysRevLett.63.109.
[4]
WANG J S, SWENDSEN R H, and KOTECKY R. Three- state antiferromagnetic potts models: A Monte Carlo study[J]. Physical Review B, 1990, 42(4): 2465-2474. doi: 10.1103/ PhysRevB.42.2465.
[5]
VIGODA E. Improved bounds for sampling colorings[J]. Journal of Mathematical Physics, 2000, 41(3): 51-59. doi: 10.1063/1.533196.
[6]
FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001-8708 (77)90061-5.
[7]
MEYNIEL H. Les 5-colorations d'un graphe planaire forment une classe de commutation unique[J]. Journal of Combinatorial Theory Series B, 1978, 24(3): 251-257. doi: 10.1016/0095-8956(78)90042-4.
[8]
MOHAR B. Kempe Equivalence of Colorings[M]. Graph Theory in Paris. Birkhäuser Basel, 2006: 287-297. doi: 10.1007/978-3-7643-7400-6_22.
[9]
VERGNAS M L and MEYNIEL H. Kempe classes and the Hadwiger conjecture[J]. Journal of Combinatorial Theory Series B, 1981, 31(1): 95-104. doi: 10.1016/S0095-8956(81) 80014-7.
[10]
BERTSCHI M E. Perfectly contractile graphs[J]. Journal of Combinatorial Theory, Series B, 1990, 50(2): 222-230. doi: 10.1016/0095-8956(90)90077-D.
[11]
MEYNIEL H. The graphs whose odd cycles have at least two chords[J]. Annals of Discrete Mathematics, 1984, 88(21): 115-119. doi: 10.1016/S0304-0208(08)72927-X.
[12]
FEGHALI C, JOHNSON M, and PAULUSMA D. Kempe cquivalence of colourings of cubic graphs[J]. European Journal of Combinatorics, 2017, 59(2): 1-10. doi: 10.1016/ j.ejc.2016.06.008.
[13]
MCDONALD J, MOHAR B, and SCHEIDE D. Kempe equivalence of edge-colorings in subcubic and subquartic graphs[J]. Journal of Graph Theory, 2012, 70(2): 226-239. doi: 10.1002/jgt.20613.
[14]
BELCASTRO S M and HAAS R. Counting edge-Kempe- equivalence classes for 3-edge-colored cubic graphs[J]. Discrete Mathematics, 2014, 325(13): 77-84. doi: 10.1016/j. disc.2014.02.014.
XU J. Theory on structure and coloring of maximal planar graphs (2) Domino configurations and extending- ccontracting operations[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1271-1327. doi: 10. 11999/JEIT160224.
XU J. Theory on structure and coloring of maximal planar graphs (4):σ-operations and Kempe equivalent classes[J]. Journal of Electronics & Information Technology, 2016, 38(7): 1557-1585. doi: 10.11999/JEIT160483.
[17]
BROOKS R L. On colouring the nodes of a network[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37(2): 194-197. doi: http://dx.doi.org/10.1017 /S030500410002168X.
