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

XU Jin

doi:10.11999/JEIT160409

Volume 38 Issue 6

Jun. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(6): 1328-1353

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

Citation:

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

Citation:

PDF( 1031 KB)

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

doi: 10.11999/JEIT160409

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)

Received Date: 2016-04-22
Rev Recd Date: 2016-04-26
Publish Date: 2016-06-19

Abstract

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).

FullText(HTML)

References(43)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views