极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想

许进

doi:10.11999/JEIT160409

极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想

doi: 10.11999/JEIT160409

许进¹

基金项目:

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

计量
- 文章访问数: 1722
- HTML全文浏览量: 185
- PDF下载量: 679
- 被引次数: 0
出版历程
- 收稿日期: 2016-04-22
- 修回日期: 2016-04-26
- 刊出日期: 2016-06-19

Theory on Structure and Coloring of Maximal Planar Graphs (3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures

XU Jin¹

Funds:

The National 973 Program of China (2013CB 329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

摘要

摘要: 一个极大平面图若是从K4出发，不断地在三角面上嵌入3度顶点得到的，则称此极大平面图为递归极大平面图。唯一4-色极大平面图猜想是指：一个平面图是唯一4-可着色的当且仅当它是递归极大平面图。此猜想已有43年历史，是图着色理论中继四色猜想之后另一个著名的未解猜想。为此，该文相继深入研究了哑铃极大平面图与递归极大平面图的结构与特性，结合该系列文章(2)的扩缩运算，给出了证明唯一4-色极大平面图猜想的一种思路。
- 唯一4-色极大平面图猜想 /
- 纯树着色猜想 /
- 哑铃极大平面图 /
- 递归极大平面图
Abstract: A maximal planar graph is called the recursive maximal planar graph if it can be obtained fromK4 by embedding a 3-degree vertex in some triangular face continuously. The uniquely 4-colorable maximal planar graph conjecture states that a planar graph is uniquely 4-colorable if and only if it is a recursive maximal planar graph. This conjecture, which has 43 years of history, is a very influential conjecture in graph coloring theory after the Four-Color Conjecture. In this paper, the structures and properties of dumbbell maximal planar graphs and recursive maximal planar graphs are studied, and an idea of proving the uniquely 4-colorable maximal planar graph conjecture is proposed based on the extending-contracting operation proposed in this series of article (2).

HTML全文

参考文献(43)

GREENWELL D and KRONK H V. Uniquely line-colorable graphs[J]. Canadian Mathematical Bulletin, 1973, 16(4): 525-529. doi: 10.4153/CMB-1973-086-2.

GLEASON T C and CARTWRIGHT F D. A note on a matrix criterion for unique colorability of assigned graph[J]. Psychometrika, 1967, 32(3): 291-296. doi: 10.1007/ BF02289592.

CARTWRIGHT F D and HARARY F. On the coloring of signed graphs[J]. Elemente Der Mathematik, 1968, 23(4): 85-89.

HARARY F, HEDETNIEMI S T, and ROBINSON R W. Uniquely colorable graphs[J]. Journal of Combinatorial Theory, 1969, 6(3): 264-270. doi: 10.1016/S0021-9800(69) 80086-4.

NESTRIL J. On critical uniquely colorable graphs[J]. Archiv Der Mathematics, 1972, 23(1): 210-213. doi: 10.1007/ BF01304871.

NESTRIL J. On uniquely colorable graphs without short cycles[J]. Casopis Pro Pěstovn Matematiky, 1973, 98(2): 122-125.

GREENWELL D and LOVASZ L. Applications of product coloring[J]. Acta Mathematica Academiae Scientiarum Hungaricae, 1974, 25(3): 335-340. doi: 10.1007/BF01886093.

MULLER V. On colorable critical and uniquely colorable critical graphs[J]. Recent Advances in Graph Theory, 1974: 385-386.

MULLER V. On coloring of graphs without short cycles[J]. Discrete Mathematics, 1979, 26(2): 165-176. doi: 10.1016/ 0012-365X(79)90121-3.

AKSIONOV V A. Chromatically connected vertices in planar graphs[J]. Diskret Analiz, 1977, 31(31): 5-16.

MELNIKOV L S and STEINBERG R. One counterexample for two conjectures on three coloring[J]. Discrete Mathematics, 1977, 20(77): 203-206. doi: 10.1016/0012-365X (77)90059-0.

WANG C C and ARTZY E. Note on the uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1973, 15(2): 204-206. doi: 10.1016/0095-8956(73)90022-1.

OSTERWEIL L J. Some classes of uniquely 3-colorable graphs[J]. Discrete Mathematics, 1974, 8(1): 59-69. doi: 10. 1016/0012-365X(74)90110-1.

BOLLOBAS B and SAUER N W. Uniquely colorable graphs with large girth[J]. Canadian Journal of Mathematics, 1976, 28(6): 1340-1344. doi: 10.4153/CJM-1976-133-5.

DMITRIEV I G. Weakly cyclic graphs with integral chromatic spectra[J]. Metody Diskret Analiz, 1980, 34(34): 3-7.

BOLLOBAS B. Uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1978, 25(1): 54-61. doi: 10.1016/S0095-8956(78)80010-0.

XU S J. The size of uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1990, 50(2): 319-320. doi: 10.1016/0095-8956(90)90086-F.

CHAO C and CHEN Z. On uniquely 3-colorable graphs[J]. Discrete Mathematics, 1993, 112(1): 21-27. doi: 10.1016/0012- 365X(93)90220-N.

AKBARI S, MIRROKNI V S, and SADJAD B S.-free uniquely vertex colorable graphs with minimum possible edges[J]. Journal of Combinatorial Theory, Series B, 2001, 82(2): 316-318. doi: 10.1006/jctb.2000.2028.

FIORINI S. On the chromatic index of a graph, III: Uniquely edge-colorable graphs[J]. Quarterly Journal Mathematics, 1975, 26(3): 129-140.

THOMASON A G. Hamiltonian cycles and uniquely edge colorable graphs[J]. Annals of Discrete Mathematics, 1978, 3: 259-268. doi: 10.1016/S0167-5060(08)70511-9.

THOMASON A G. Cubic graphs with three Hamiltonian cycles are not always uniquely edge Colorable[J]. Journal of Graph Theory, 1982, 6(2): 219-221. doi: 10.1002/jgt. 3190060218.

FIORINI S and WILSON R J. Edge colouring of graphs[J]. Research Notes in Mathematics, 1977, 23(1): 237-239.

ZHANG C Q. Hamiltonian weights and unique edge-3- colorings of cubic graphs[J]. Journal of Graph Theory, 1995, 20(1): 91-99. doi: 10.1002/jgt.3190200110.

GOLDWASSER J L and ZHANG C Q. On the minimal counterexamples to a conjecture about unique edge-3- coloring[J]. Congressus Numerantium, 1996, 113: 143-152.

GOLDWASSER J L and ZHANG C Q. Uniquely edge- colorable graphs and Snarks[J]. Graphs and Combinatorics, 2000, 16(3): 257-267. doi: 10.1007/PL00007221.

KRIESELL M. Contractible non-edges in 3-connected graphs [J]. Journal of Combinatorial Theory, Series B, 1998, 74(2): 192-201. doi: 10.1006/jctb.1998.1842.

FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001- 8708(77)90061-5.

FOWLER T. Unique coloring of planar graphs[D]. [Ph. dissertation], Georgia Institute of Technology, 1998: 19-55.

CHARTRAND G and GELLER D. On uniquely colorable planar graphs[J]. Journal of Combinatorial Theory, 1969, 6(3): 271-278. doi: 10.1016/S0021-9800(69)80087-6.

AKSIONOV V A. On uniquely 3-colorable planar graphs[J]. Discrete Mathematics, 1977, 20(3): 209-216. doi: 10.1016/ 0012-365X(77)90061-9.

MATSUMOTO N. The size of edge-critical uniquely 3-colorable planar graphs[J]. The Electronic Journal of Combinatorics, 2013, 20(4): 1823-1831.

LI Z P, ZHU E Q, SHAO Z H, et al. Size of edge-critical uniquely 3-colorable planar graphs[J]. Discrete Mathematics, 2016, 339(4): 1242-1250. doi: 10.1016/j.disc.2015.11.009.

LI Z P, ZHU E Q, SHAO Z H, et al. A note on uniquely 3-colorable planar graphs[J]. International Journal of Computer Mathematics, 2016: 1-8. doi: 10.1080/00207160. 2016.1167196.

BOHME T, STIEBITZ M, VOIGT M, et al. On uniquely 4-colorable planar graphs[OL]. url=cite-seer.ist.psu.edu/ 110448.html.1998.

DAILEY D P. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete[J]. Discrete

Mathematics, 1980, 30(3): 289-293. doi: 10.1016/0012- 365X(80)90236-8.

XU J and WEI X S. Theorems of uniquely k-colorable graphs[J]. Journal of Shaanxi Normal University (Natural Science Edition), 1995, 23: 59-62.

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

许进. 极大平面图的结构与着色理论: (2)多米诺构形与扩缩运算[J]. 电子与信息学报, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.

XU Jin. Theory on the 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.

ZHU E Q, LI Z P, SHAO Z H, et al. Acyclically 4-colorable triangulations[J]. Information Processing Letters, 2016, 116(6): 401-408. doi: 10.1016/j.ipl.2015.12.005.

XU J, LI Z P, and ZHU E Q. On purely tree- colorable planar graphs[J]. Information Processing Letters, 2016, 116(8): 532-536. doi: 10.1016/j.ipl.2016.03.011.

施引文献

资源附件(0)

访问统计