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

许进

doi:10.11999/JEIT160483

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

doi: 10.11999/JEIT160483

许进¹

基金项目:

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

计量
- 文章访问数: 1470
- HTML全文浏览量: 113
- PDF下载量: 802
- 被引次数: 0
出版历程
- 收稿日期: 2016-05-11
- 修回日期: 2016-05-30
- 刊出日期: 2016-07-19

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

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)

摘要

摘要: 设G是一个k-色图，若G的所有k-着色是Kempe等价的，则称G为Kempe图。表征色数3的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究，其主要贡献是：(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳，故对2-色耳的特征进行了深入研究；(2)引入-特征图，清晰地刻画了一个图中所有4-着色之间的关联关系，并深入研究了-特征图的性质；(3)揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型，圈型和循环圈型，并指出这3种类型可同时存在于一个极大平面图的4-着色集中；(4)研究了Kempe极大平面图特征，给出了该类图的多米诺递推构造法，以及两个Kempe极大平面图猜想。
- Kempe极大平面图 /
- Kempe变换 /
- -运算 /
- Kempe等价类 /
- -特征图 /
- 2-色耳
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

HTML全文

参考文献(29)

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.

施引文献

资源附件(0)

访问统计