2016, 38(4): 763-779.
doi: 10.11999/JEIT160072
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.