Kempe变换理论研究进展

doi:10.11999/JEIT161299

Abstract
Figure/Table
References (27)
Related Citation (4)

Download: PDF (385 KB)
Export: BibTeX | EndNote (RIS)

Abstract

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. Since Kempe introduced Kempe changes in his false proof of the Four Color Theorem in 1879, many scholars devote to the research on Kempe changes from different points of view. The main contributions in this paper are as follows: (1) Some basic properties of Kempe changes are summarized; (2) A series of important results with regard to Kempe changes are to be reviewed and analyzed in detail; (3) Another novel and more brief proof method of Meyniel Theorem, that all 5-colorings of a planar graph are Kempe equivalent, is given out; (4) A problem related with types of colorings is proposed here, which intends to explore the relationships between different Kempe equivalent classes, and thus contributes to the further study.

Key words： Kempe changes Kempe equivalent class Tree-colored Cycle-colored

Received: 28 December 2016 Published: 03 January 2017

PACS:

O157.5

Fund:

The National 973 Program of China (2013CB329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

Corresponding Authors: XU Jin E-mail: jxu@pku.edu.cn

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	XU Jin
	LIU Xiaoqing

Cite this article:

XU Jin,LIU Xiaoqing. Research Progress on the Theory of Kempe Changes[J]. JEIT, 2017, 39(6): 1493-1502.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT161299 OR http://jeit.ie.ac.cn/EN/Y2017/V39/I6/1493

[1]	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]	BONDY J A and MURTY U S R. Graph Theory[M]. New York, USA, Springer, 2008: 1-581.
[3]	HEAWOOD P J. Map colour theorem[J]. The Quarterly Journal of Mathematics, 1890, 24: 332-338.
[4]	MUHLENTHALER M and WANKA R. The connectedness of clash-free timetables[C]. 10th International Conference of the Practice and Theory of Automated Timetabling PATAT 2014, York, United Kindom, 2014: 330-346.
[5]	WANG J S, SWENDSEN R H, and KOTECKY R. Antiferromagnetic potts models[J]. Physical Review Letters, 1989, 63(2): 109-112.
[6]	WANG J S, SWENDSEN R H, and KOTECK R. Three-state antiferromagnetic potts models: A monte carlo study[J]. Physical Review B Condensed Matter, 1990, 42(4): 2465-2474.
[7]	VIGODA E. Improved bounds for sampling colorings[J]. Journal of Mathematical Physics, 41(3): 1555-1569. doi: 10. 1063/1.533196.
[8]	许进. 极大平面图的结构与着色理论(4): -运算与Kempe等价类[J]. 电子与信息学报, 2016, 38(7): 1557-1585. doi: 10.11999/JEIT160483.
	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.
[9]	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.
[10]	FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001-8708 (77)90061-5.
[11]	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.
[12]	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.
[13]	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.
[14]	FEGHALI C, JOHNSON M, and PAULUSMA D. Kempe equivalence of colourings of cubic graphs[J]. Electronic Notes in Discrete Mathematics, 2015, 49: 243-249. doi: 10.1016/ j.endm.2015.06.034.
[15]	BONAMY M, BOUSQUET N, FEGHALI C, et al. On a conjecture of mohar concerning Kempe equivalence of regular graphs[J]. Discrete Mathematics. arXiv:1510.06964v3 [cs.DM] 22 Sep 2016.
[16]	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.
[17]	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.
[18]	HEUVEL JAN VAN DEN. The complexity of change[J]. Surveys in Combinatorics. arXiv: 1312.2816v1[cs.DM] 10 Dec 2013.
[19]	CERECEDA L, HEUVEL J V D, and JOHNSON M. Connectedness of the graph of vertex-colourings[J]. Discrete Mathematics, 2008, 308(5/6): 913-919. doi: 10.1016/j.disc. 2007.07.028.
[20]	CERECEDA L, HEUVEL J VAN DEN, and JOHNSON M. Finding paths between 3-colorings[J]. Journal of Graph Theory, 2011, 67(1): 69-82.
[21]	BONSMA P and CERECEDA L. Finding paths between graph colourings: PSPACE-completeness and superpolynominall distances[J]. Theoretical Computer Science, 2007, 410(50): 738-749. doi: 10.1016/j.tcs.2009.08. 023.
[22]	JERRUM M. A very simple algorithm for estimating the number of -colorings of a low-degree graph[J]. Random Structures & Algorithms, 1995, 7(2): 157-165.
[23]	CERECEDA L. Mixing graph colourings[D]. [Ph.D. dissertation], London School of Economics and Political Science, 2007.
[24]	BONAMY M and BOUSQUET N. Recoloring bounded treewidth graphs[J]. Electronic Notes in Discrete Mathematics, 2013, 44(5): 257-262. doi: 10.1016/j.endm. 2013.10.040.
[25]	BONAMY M, JOHNSON M, LIGNOS I M, et al. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[J]. Journal of Combinatorial Optimization, 2014, 27: 132-143. doi: 10.1007/s10878-012- 9490-y.
[26]	FEGHALI C, JOHNSON M, and PAULUSMA D. A reconfigurations analogue of brooks’ theorem[J]. Journal of Graph Theory, 2015, 8635: 287-298. doi: 10.1007/978-3- 662-44465-8_25.
[27]	BOUSQUET N and PERARNAU G. Fast recoloring of sparse graphs[J]. European Journal of Combinatorics, 2016, 52A: 1-11. doi: 10.1016/j.ejc.2015.08.001.