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.
许进. 极大平面图的结构与着色理论 (1)色多项式递推公式与四色猜想[J]. 电子与信息学报, 2016, 38(4): 763-779.
XU Jin. Theory on the Structure and Coloring of Maximal Planar Graphs (1)Recursion Formula of Chromatic Polynomial and FourColor Conjecture. JEIT, 2016, 38(4): 763-779.
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.
[5]
KEMPE A B. On the geographical problem of the four colors [J]. American Journal of Mathematics, 1879, 2(3): 193-200.
[6]
HEAWOOD P J. Map colour theorem[J]. Quarterly Journal of Mathematics, 1890, 24: 332-338.
[7]
APPEL K and HAKEN W. The solution of the four-color map problem[J]. Science American, 1977, 237(4): 108-121.
[8]
APPEL K and HAKEN W. Every planar map is four colorable, I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429-490.
[9]
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.
[10]
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.
[11]
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.
[12]
WERNICKE P. den kartographischen Vierfarbensatz [J]. Mathematische Annalen, 1904, 58(3): 413-426.
[13]
BIRKHOFF G D. The reducibility of maps[J]. American Journal of Mathematics, 1913, 35(2): 115-128.
[14]
HEESCH H. Untersuchungen Zum Vierfarbenproblem[M]. Mannheim/Wien/Z?urich: Bibliographisches Institut, 1969: 4-12.
[15]
FRANKLIN P. The four color problem[J]. American Journal of Mathematics, 1922, 44(3): 225-236.
[16]
FRANKLIN P. Note on the four color problem[J]. Journal of Mathematical Physics, 1938, 16: 172-184.
[17]
REYNOLDS C. On the problem of coloring maps in four colors[J]. Annals of Mathematics, 1926-27, 28(1-4): 477-492.
[18]
WINN C E. On the minimum number of polygons in an irreducible map[J]. American Journal of Mathematics, 1940, 62(1): 406-416.
[19]
ORE O and STEMPLE J. Numerical calculations on the four-color problem[J]. Journal of Combinatorial Theory, 1970, 8(1): 65-78.
[20]
MAYER J. Une propriètè des graphes minimaux dans le probl?eme des quatre couleurs[J]. Problèmes Combinatoires et Thorie des Graphes, Colloques Internationaux CNRS, 1978, 260: 291-295.
[21]
TAIT P G. Remarks on the colouring of maps[J]. Proceedings of the Royal Society of Edinburgh, 1880, 10: 501-516.
[22]
PETERSEN J. Surle théorème de Tait[J]. L'intermédiaire des Mathématiciens, 1898, 5: 225-227.
[23]
TUTTE W T. On Hamiltonian circuits[J]. Journal of the London Mathematical Society, 1946, 21: 98-101.
[24]
GRINBERG E J. Plane homogeneous graphs of degree three without Hamiltonian circuits[J]. Latvian Math Yearbook, 1968, 5: 51-58.
[25]
BIRKHOFF G D. A determinantal formula for the number of ways of coloring a map[J]. Annals of Mathematics, 1912, 14: 42-46.
[26]
BIRKHOFF G D and LEWIS D. Chromatic polynomials[J]. Transactions of the American Mathematical Society, 1946, 60: 355-451.
[27]
DONG F M, KOH K M, and TEO K L. Chromatic Polynomials and Chromaticity of Graphs[M]. World Scientific, Singapore, 2005: 23-215.
[28]
TUTTE W T. On chromatic polynomials and the golden ratio[J]. Journal of Combinatorial Theory, 1970, 9(3): 289-296.
[29]
TUTTE W T. Chromatic sums for planar triangulations, V: Special equations[J]. Canadian Journal of Mathematics, 1974, 26: 893-907.
[30]
READ R C. An introduction to chromatic polynomials[J]. Journal of Combinatorial Theory, 1968, 4(1): 52-71.
[31]
WHITNEY H. On the coloring of graphs[J]. Annals of Mathematics, 1932, 33(4): 688-718.
[32]
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.
[33]
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.
[34]
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.
