Research Progress on the Theory of Kempe Changes

XU Jin; LIU Xiaoqing

doi:10.11999/JEIT161299

Volume 39 Issue 6

Jun. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(6): 1493-1502

XU Jin, LIU Xiaoqing. Research Progress on the Theory of Kempe Changes[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1493-1502. doi: 10.11999/JEIT161299

Citation:

XU Jin, LIU Xiaoqing. Research Progress on the Theory of Kempe Changes[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1493-1502. doi: 10.11999/JEIT161299

XU Jin, LIU Xiaoqing. Research Progress on the Theory of Kempe Changes[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1493-1502. doi: 10.11999/JEIT161299

Citation:

XU Jin, LIU Xiaoqing. Research Progress on the Theory of Kempe Changes[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1493-1502. doi: 10.11999/JEIT161299

PDF( 384 KB)

Research Progress on the Theory of Kempe Changes

doi: 10.11999/JEIT161299

XU Jin¹,
LIU Xiaoqing¹

Funds:

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

Received Date: 2016-12-28
Rev Recd Date: 2017-01-03
Publish Date: 2017-06-19

Abstract

Abstract

Given a graphG and a proper vertex coloring ofG, a 2-coloring induced subgraph ofG 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.
- Kempe changes,
- Kempe equivalent class,
- Tree-colored,
- Cycle-colored,

FullText(HTML)

References(28)

References

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.

BONDY J A and MURTY U S R. Graph Theory[M]. New York, USA, Springer, 2008: 1-581.

HEAWOOD P J. Map colour theorem[J]. The Quarterly Journal of Mathematics, 1890, 24: 332-338.

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.

WANG J S, SWENDSEN R H, and KOTECKY R. Antiferromagnetic potts models[J]. Physical Review Letters, 1989, 63(2): 109-112.

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.

VIGODA E. Improved bounds for sampling colorings[J]. Journal of Mathematical Physics, 41(3): 1555-1569. doi: 10. 1063/1.533196.

许进. 极大平面图的结构与着色理论(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.

MOHAR B. Kempe Equivalence of Colorings[M]. Graph Theory in Paris. Birkhuser Basel, 2006: 287-297. doi: 10.1007/978-3-7643-7400-6_22.

FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001-8708 (77)90061-5.

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.

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.

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.

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.

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.

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.

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.

HEUVEL JAN VAN DEN. The complexity of change[J]. Surveys in Combinatorics. arXiv: 1312.2816v1[cs.DM] 10 Dec 2013.

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.

CERECEDA L, HEUVEL J VAN DEN, and JOHNSON M. Finding paths between 3-colorings[J]. Journal of Graph Theory, 2011, 67(1): 69-82.

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.

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.

CERECEDA L. Mixing graph colourings[D]. [Ph.D. dissertation], London School of Economics and Political Science, 2007.

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.

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.

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.

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.

Relative Articles

Supplements(0)

Cited By

Proportional views