Kempe變換理論研究進展

許進; 劉小青

doi:10.11999/JEIT161299

Kempe變換理論研究進展

doi: 10.11999/JEIT161299 cstr: 32379.14.JEIT161299

許進¹,
劉小青¹

基金項目:

國家973計劃項目(2013CB329600)，國家自然科學基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

計量
- 文章訪問數(shù): 1241
- HTML全文瀏覽量: 188
- PDF下載量: 422
- 被引次數(shù): 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變換的一些基本性質(zhì)；對已有的一些重要成果進行了較為詳細的綜述；針對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)

訪問統(tǒng)計