Kempe变换理论研究进展

许进; 刘小青

doi:10.11999/JEIT161299

Kempe变换理论研究进展

doi: 10.11999/JEIT161299

许进¹,
刘小青¹

基金项目:

国家973计划项目(2013CB329600)，国家自然科学基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

计量
- 文章访问数: 1171
- HTML全文浏览量: 174
- PDF下载量: 420
- 被引次数: 0
出版历程
- 收稿日期: 2016-12-28
- 修回日期: 2017-01-03
- 刊出日期: 2017-06-19

Research Progress on the Theory of Kempe Changes

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)

摘要

摘要: 给定一个图G及它的一个正常顶点着色f, G中所有着两种颜色之一的顶点构成的顶点子集导出的子图称为G的一个2-色导出子图，该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。自从1879年KEMPE引入Kempe变换用于证明四色猜想至今，有众多学者从不同的角度对Kempe变换展开了研究。该文总结了Kempe变换的一些基本性质；对已有的一些重要成果进行了较为详细的综述；针对MEYNIEL定理，即每个平面图的所有5-着色构成一个Kempe等价类，给出了一个新的更加简短的证明方法；提出了一个与着色类型相关的问题，意在探索不同Kempe等价类之间的关系，以助于Kempe变换的进一步研究。
- Kempe变换 /
- Kempe等价的 /
- Kempe等价类 /
- 树着色 /
- 圈着色
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 /

HTML全文

参考文献(28)

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.

施引文献

资源附件(0)

访问统计