Theory on Structure and Coloring of Maximal Planar Graphs (4)-Operations and Kempe Equivalent Classes

XU Jin

doi:10.11999/JEIT160483

Volume 38 Issue 7

Jul. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(7): 1557-1585

XU Jin. 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

Citation:

XU Jin. 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

Citation:

PDF( 1486 KB)

Theory on Structure and Coloring of Maximal Planar Graphs (4)-Operations and Kempe Equivalent Classes

doi: 10.11999/JEIT160483

XU Jin¹

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-05-11
Rev Recd Date: 2016-05-30
Publish Date: 2016-07-19

Abstract

Abstract

Let G be a k-chromatic graph.G is called a Kempe graph if all k-colorings ofG are Kempe equivalent. It is an unsolved and hard problem to characterize the properties of Kempe graphs with chromatic number3. 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.
- Kempe maximal planar graph,
- Kempe transformation,
- -operation,
- Kempe equivalent class,
- -characteristic graph,
- 2-chromatic ear

FullText(HTML)

References(29)

References

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.

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.

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.

许进, 李泽鹏, 朱恩强. 极大平面图理论研究进展[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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

BONDY J A and MURTY U S R. Graph Theory[M]. Springer, 2008: 6-58.

Relative Articles

Supplements(0)

Cited By

Proportional views