極大平面圖的結(jié)構(gòu)與著色理論 (1)色多項式遞推公式與四色猜想
doi: 10.11999/JEIT160072
基金項目:
國家973規(guī)劃項目(2013CB329600),國家自然科學(xué)基金(61472012, 6152046, 6152012, 61572492, 61372191, 61472012)
Theory on the Structure and Coloring of Maximal Planar Graphs (1)Recursion Formula of Chromatic Polynomial and FourColor Conjecture
Funds:
The National 973 Program of China (2013CB329600), The National Natural Science Foundation of China (61472012, 6152046, 6152012, 61572492, 61372191, 61472012)
-
摘要: 該文給出了極大平面圖$G$的色多項式遞推計算公式:若$\delta(G)=4$, $W_4^\nu$是$G$中輪心為$\nu$,輪圈為$\nu_1\nu_2\nu_3\nu_4\nu_1$的4-輪,則$f(G,4)=f(G_1,4)+f(G_2,4)$,其中$G_1=(G-\nu)\circ{\nu_1,\nu_3}$, $G_2=(G-\nu)\circ{\nu_2,\nu_4}$;若$\delta(G)=5$,$W_5^\nu$是$G$中$\nu$為輪心,以$\nu_1\nu_2\nu_3\nu_4\nu_5\nu_1$為輪圈的5-輪,則$f(G,4)=[f(G_1,4)-f(G_1\cup{\nu_1\nu_4,\nu_1\nu_3},4)] +[f(G_2,4)-f(G_2\cup {\nu_3\nu_1,\nu_3\nu_5},4)]+ [f(G_3,4)-f(G_3\cup {\nu_1\nu_4},4)]$,其中$G_1=(G-\nu)\circ{\nu_2,\nu_5}$, $G_2=(G-\nu)\circ{\nu_2,\nu_4}$, $G_3=(G-\nu)\circ{\nu_3,\nu_5}$,“$\circ$”表示收縮運算;進而討論了使用公式證明四色猜想的應(yīng)用:將四色猜想轉(zhuǎn)化成研究一種特殊圖類:4-色漏斗型偽唯一4-色極大平面圖。Abstract: In this paper, two recursion formulae of chromatic polynomial of a maximal planar graph $G$ are obtained: when $\delta(G)=4$, let $W_4^\nu$ be a 4-wheel of $G$ with wheel-center $\nu$ and wheel-cycle $\nu_1\nu_2\nu_3\nu_4\nu_1$, then $f(G,4)=f((G,4)\circ{\nu_1,\nu_3},4)+ f((G,4)\circ{\nu_2,\nu_4},4)$; when $\delta(G)=5$, let $W_5^\nu$ a 5-wheel of $G$ with wheel-center $\nu$ and wheel-cycle $\nu_1\nu_2\nu_3\nu_4\nu_5\nu_1$, then $f(G,4)=[f(G_1,4)-f(G_1\cup{\nu_1\nu_4,\nu_1\nu_3},4)] +[f(G_2,4)-f(G_2\cup {\nu_3\nu_1,\nu_3\nu_5},4)]+ [f(G_3,4)-f(G_3\cup {\nu_1\nu_4},4)]$, $G_1=(G-\nu)\circ{\nu_2,\nu_5}$, $G_2=(G-\nu)\circ{\nu_2,\nu_4}$, $G_3=(G-\nu)\circ{\nu_3,\nu_5}$, where $“\circ”$ denotes the operation of vertex contraction. Moreover, the application of the above formulae to the proof of Four-Color Conjecture is investigated. By using these formulae, the proof of Four-Color Conjecture boils down to the study on a special class of graphs, viz., 4-chromatic-funnel pseudo uniquely-4-colorable maximal planar graphs.
-
JENSEN T R and TOFT B. Graph Coloring Problems[M]. New York: John Wiley Sons, 1995: 48-49. DAZ J, PETIT J, and SERNA M. A survey of graph layout problems[J]. ACM Computing Surveys, 2002, 34(3): 313-355. BRODER A, KUMAR R, MAGHOUL F, et al. Graph structure in the Web[J]. Computer Networks, 2000, 33(1-6): 309-320. 許進, 李澤鵬, 朱恩強. 極大平面圖的研究進展[J]. 計算機學(xué)報, 2015, 38(7): 1680-1704. XU Jin, LI Zepeng, and ZHU Enqiang. Research progress on the theory of maximal planar graphs[J]. Chinese Journal of Computers, 2015, 38(7): 1680-1704. KEMPE A B. On the geographical problem of the four colors [J]. American Journal of Mathematics, 1879, 2(3): 193-200. HEAWOOD P J. Map colour theorem[J]. Quarterly Journal of Mathematics, 1890, 24: 332-338. APPEL K and HAKEN W. The solution of the four-color map problem[J]. Science American, 1977, 237(4): 108-121. APPEL K and HAKEN W. Every planar map is four colorable, I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429-490. APPEL K, HAKEN W, and KOCH J. Every planar map is four-colorable, II: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21(3): 491-567. ROBERTSON N, SANDERS D P, SEYMOUR P, et al. A new proof of the four colour theorem[J]. Electronic Research Announcements American Mathematical Society, 1996, 2: 17-25. ROBERTSON N, SANDERS D P, SEYMOUR P D, et al. The four color theorem[J]. Journal of Combinatorial Theory, Series B, 1997, 70(1): 2-44. WERNICKE P. den kartographischen Vierfarbensatz [J]. Mathematische Annalen, 1904, 58(3): 413-426. BIRKHOFF G D. The reducibility of maps[J]. American Journal of Mathematics, 1913, 35(2): 115-128. HEESCH H. Untersuchungen Zum Vierfarbenproblem[M]. Mannheim/Wien/Z?urich: Bibliographisches Institut, 1969: 4-12. FRANKLIN P. The four color problem[J]. American Journal of Mathematics, 1922, 44(3): 225-236. FRANKLIN P. Note on the four color problem[J]. Journal of Mathematical Physics, 1938, 16: 172-184. REYNOLDS C. On the problem of coloring maps in four colors[J]. Annals of Mathematics, 1926-27, 28(1-4): 477-492. WINN C E. On the minimum number of polygons in an irreducible map[J]. American Journal of Mathematics, 1940, 62(1): 406-416. ORE O and STEMPLE J. Numerical calculations on the four-color problem[J]. Journal of Combinatorial Theory, 1970, 8(1): 65-78. MAYER J. Une proprit des graphes minimaux dans le probl?eme des quatre couleurs[J]. Problmes Combinatoires et Thorie des Graphes, Colloques Internationaux CNRS, 1978, 260: 291-295. TAIT P G. Remarks on the colouring of maps[J]. Proceedings of the Royal Society of Edinburgh, 1880, 10: 501-516. PETERSEN J. Surle thorme de Tait[J]. L'intermdiaire des Mathmaticiens, 1898, 5: 225-227. TUTTE W T. On Hamiltonian circuits[J]. Journal of the London Mathematical Society, 1946, 21: 98-101. GRINBERG E J. Plane homogeneous graphs of degree three without Hamiltonian circuits[J]. Latvian Math Yearbook, 1968, 5: 51-58. BIRKHOFF G D. A determinantal formula for the number of ways of coloring a map[J]. Annals of Mathematics, 1912, 14: 42-46. BIRKHOFF G D and LEWIS D. Chromatic polynomials[J]. Transactions of the American Mathematical Society, 1946, 60: 355-451. DONG F M, KOH K M, and TEO K L. Chromatic Polynomials and Chromaticity of Graphs[M]. World Scientific, Singapore, 2005: 23-215. TUTTE W T. On chromatic polynomials and the golden ratio[J]. Journal of Combinatorial Theory, 1970, 9(3): 289-296. TUTTE W T. Chromatic sums for planar triangulations, V: Special equations[J]. Canadian Journal of Mathematics, 1974, 26: 893-907. READ R C. An introduction to chromatic polynomials[J]. Journal of Combinatorial Theory, 1968, 4(1): 52-71. WHITNEY H. On the coloring of graphs[J]. Annals of Mathematics, 1932, 33(4): 688-718. XU Jin. Recursive formula for calculating the chromatic polynomial of a graph by vertex deletion[J]. Acta Mathematica Scientia Series B, 2004, 24B(4): 577-582. XU Jin and LIU Z. The chromatic polynomial between graph and its complementAbout Akiyama and Hararys, open problem[J]. Graph and Combinatorics, 1995, 11: 337-345. ZYKOV A A. On some properties of linear complexes[J]. Math Ussr Sbornik, 1949, 24(66): 163-188 (in Russian); English Translation in Transactions of the American Mathematical Society, 1952, 79. -
計量
- 文章訪問數(shù): 2660
- HTML全文瀏覽量: 118
- PDF下載量: 1015
- 被引次數(shù): 0