极大平面图的结构与着色理论 (4) <em>σ</em>-运算与Kempe等价类

doi:10.11999/JEIT160483

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

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

Abstract

Let G be a k-chromatic graph. G is called a Kempe graph if all k-colorings of G are Kempe equivalent. It is an unsolved and hard problem to characterize the properties of Kempe graphs with chromatic number ≥3. The Kempe equivalence of maximal planar graphs is addressed in this paper. Our contributions are as follows: (1) Observe and study a class of subgraphs, called 2-chromatic ears, which play a critical role in guaranteeing the Kempe equivalence between two 4-colorings; (2) Introduce and explore the properties of σ-characteristic graphs, which clearly characterize the relations of all 4-colorings of a graph; (3) Divide the Kempe equivalent classes of non-Kempe 4-chromatic maximal planar graphs into three classes, tree-type, cycle-type, and circular-cycle-type, and point out that all these three classes can exist simultaneously in the set of 4-colorings of one maximal planar graph; (4) Study the characteristics of Kempe maximal planar graphs, introduce a recursive domino method to construct such graphs, and propose two conjectures.

Key words： Kempe maximal planar graph Kempe transformation σ-operation Kempe equivalent class σ-characteristic graph 2-chromatic ear

Received: 11 May 2016 Published: 02 June 2016

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

Cite this article:

XU Jin. Theory on Structure and Coloring of Maximal Planar Graphs (4) σ-Operations and Kempe Equivalent Classes[J]. JEIT, 2016, 38(7): 1557-1585.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT160483 OR http://jeit.ie.ac.cn/EN/Y2016/V38/I7/1557

[1]	JENSEN T R and TOFT B. Graph coloring problems[J]. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995, 113(2): 29-59. doi: 10.1002/ 9781118032497.ch2.
[2]	DIAZ J, PETIT J, and SERNA M. A survey of graph layout problems[J]. ACM Computing Surveys, 2002, 34(3): 313-356. doi: 10.1145/568522.568523.
[3]	BRODER A, KUMAR R, MAGHOUL F, et al. Graph structure in the web[J]. Computer Networks, 2000, 33(1/6): 309-320. doi: 10.1016/S1389-1286(00)00083-9.
[4]	许进, 李泽鹏, 朱恩强. 极大平面图理论研究进展[J]. 计算机学报, 2015, 38(8): 1680-1704. doi: 10. 11897/SP.J.1016.2015. 01680.
	XU J, LI Z P, and ZHU E Q. Research progress on the theory of maximal planar graphs[J]. Chinese Journal of Computers, 2015, 38(8): 1680-1704. doi: 10.11897/SP.J.1016.2015. 01680.
[5]	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.
[6]	FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001- 8708(77)90061-5.
[7]	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.
[8]	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.
[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]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	FIOL M A and VILALTELLA J. A simple and fast heuristic algorithm for edge-coloring of graphs[J]. AKCE International Journal of Graphs and Combinatorics, 2013, 10(3): 263-272.
[15]	EFTHYMIOU C and SPIRAKIS P G. Random sampling of colourings of sparse random graphs with a constant number of colours[J]. Theoretical Computer Science, 2008, 407(1/3): 134-154. doi: 10.1016/j.tcs.2008.05.008.
[16]	DYER M, FLAXMAN A D, FRIEZE A M, et al. Randomly coloring sparse random graphs with fewer colors than the maximum degree[J]. Random Structures and Algorithms, 2006, 29(4): 450-465. doi: 10.1002 /rsa.20129.
[17]	HAYES T P and VIGODA E. A non-Markovian coupling for randomly sampling colorings[C]. 44th Annual Symposium on Foundations of Computer Science, 2003: 618-627. doi: 10.1109/SFCS.2003.1238234.
[18]	LUCZAK T and VIGODA E. Torpid mixing of the Wang- Swendsen-Kotecky algorithm for sampling colorings[J]. Journal of Discrete Algorithms, 2005, 3(1): 92-100. doi: 10.1016/j.jda.2004.05.002.
[19]	MORGENSTERN C A and SHAPIRO H D. Heuristics for rapidly four-coloring large planar graphs[J]. Algorithmica, 1991, 6(1): 869-891. doi: 10.1007/BF01759077.
[20]	SIBLEY T and WAGON S. Rhombic penrose tilings can be 3-colored[J]. The American Mathematical Monthly, 2000, 107(3): 251-253. doi: 10.2307/2589317.
[21]	VIGOD E. Improved bounds for sampling colorings[C]. 40th Annual Symposium on Foundations of Computer Science, New York, 1999: 51-59. doi: 10.1109/SFFCS.1999.814577.
[22]	FRIEZE A and VIGODA E. A survey on the use of markov chains to randomly sample colourings[C]. In Combinatorics, Complexity, and Chance. Oxford Lecture Ser. Math. Appl. 34 53-71. Oxford Univ. Press, Oxford. MR2314561. doi: 10.1093/acprof:oso/9780198571278.003.0004.
[23]	HAYES T P and VIGODA E. Coupling with the stationary distribution and improved sampling for colorings and independent sets[J]. The Annals of Applied Probability, 2006, 16(3): 1297-1318. doi: 10.1214/105051606000000330.
[24]	BALASUBRAMANIAN R and SUBRAMANIAN C R. On sampling colorings of bipartite graphs[J]. Discrete Mathematics and Theoretical Computer Science Dmtcs, 2006, 8(1): 17-30. [25] 许进. 极大平面图的结构与着色理论(2): 多米诺构形与扩缩运算[J]. 电子与信息学报, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.
	XU J. Theory on structure and coloring of maximal planar graphs (2): Domino configurations and extending- contracting operations[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.
[26]	许进. 极大平面图的结构与着色理论(3): 纯树着色与唯一4-色平面图猜想[J]. 电子与信息学报, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.
	XU J. Theory on structure and coloring of maximal planar graphs (3): Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.
[27]	BONDY J A and MURTY U S R. Graph Theory[M]. Springer, 2008: 6-58.