極大平面圖的結(jié)構(gòu)與著色理論 (4)-運算與Kempe等價類

許進

doi:10.11999/JEIT160483

極大平面圖的結(jié)構(gòu)與著色理論 (4)-運算與Kempe等價類

doi: 10.11999/JEIT160483

許進¹

基金項目:

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

計量
- 文章訪問數(shù): 1549
- HTML全文瀏覽量: 130
- PDF下載量: 805
- 被引次數(shù): 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圖。表征色數(shù)3的Kempe圖特征是一尚待解決難題。該文對極大平面圖的Kempe等價性進行了研究，其主要貢獻是：(1)發(fā)現(xiàn)導致兩個4-著色是Kempe等價的關鍵子圖為2-色耳，故對2-色耳的特征進行了深入研究；(2)引入-特征圖，清晰地刻畫了一個圖中所有4-著色之間的關聯(lián)關系，并深入研究了-特征圖的性質(zhì)；(3)揭示了4-色非Kempe極大平面圖的Kempe等價類可分為樹型，圈型和循環(huán)圈型，并指出這3種類型可同時存在于一個極大平面圖的4-著色集中；(4)研究了Kempe極大平面圖特征，給出了該類圖的多米諾遞推構(gòu)造法，以及兩個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] 許進. 極大平面圖的結(jié)構(gòu)與著色理論(2): 多米諾構(gòu)形與擴縮運算[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.

許進. 極大平面圖的結(jié)構(gòu)與著色理論(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)

訪問統(tǒng)計