Kempe變換理論研究進(jìn)展
doi: 10.11999/JEIT161299
基金項(xiàng)目:
國家973計(jì)劃項(xiàng)目(2013CB329600)，國家自然科學(xué)基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)
Research Progress on the Theory of Kempe Changes
Funds:
The National 973 Program of China (2013CB329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)
-
摘要: 給定一個(gè)圖G及它的一個(gè)正常頂點(diǎn)著色f, G中所有著兩種顏色之一的頂點(diǎn)構(gòu)成的頂點(diǎn)子集導(dǎo)出的子圖稱為G的一個(gè)2-色導(dǎo)出子圖，該2-色導(dǎo)出子圖的分支稱為G的一個(gè)2-色分支。Kempe變換是指將圖G的某個(gè)2-色分支實(shí)施顏色互換。自從1879年KEMPE引入Kempe變換用于證明四色猜想至今，有眾多學(xué)者從不同的角度對Kempe變換展開了研究。該文總結(jié)了Kempe變換的一些基本性質(zhì)；對已有的一些重要成果進(jìn)行了較為詳細(xì)的綜述；針對MEYNIEL定理，即每個(gè)平面圖的所有5-著色構(gòu)成一個(gè)Kempe等價(jià)類，給出了一個(gè)新的更加簡短的證明方法；提出了一個(gè)與著色類型相關(guān)的問題，意在探索不同Kempe等價(jià)類之間的關(guān)系，以助于Kempe變換的進(jìn)一步研究。
-
關(guān)鍵詞:
- Kempe變換 /
- Kempe等價(jià)的 /
- Kempe等價(jià)類 /
- 樹著色 /
- 圈著色
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.-
Key words:
- Kempe changes /
- Kempe equivalent class /
- Tree-colored /
- Cycle-colored /
-
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. 許進(jìn). 極大平面圖的結(jié)構(gòu)與著色理論(4): -運(yùn)算與Kempe等價(jià)類[J]. 電子與信息學(xué)報(bào), 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. -
計(jì)量
- 文章訪問數(shù): 1212
- HTML全文瀏覽量: 183
- PDF下載量: 421
- 被引次數(shù): 0
下載:
