极大平面图的结构与着色理论 (1)色多项式递推公式与四色猜想

来源：电子与信息学报杂志2016年第4期北京时间：

作者：许进

摘要：该文给出了极大平面图$G$的色多项式递推计算公式：若$\delta(G)=4$, $W_4^u$是$G$中轮心为$u$，轮圈为$u_1u_2u_3u_4u_1$的4-轮，则$f(G,4)=f(G_1,4)+f(G_2,4)$，其中$G_1=(G-u)\circ{u_1,u_3}$, $G_2=(G-u)\circ{u_2,u_4}$；若$\delta(G)=5$,$W_5^u$是$G$中$u$为轮心，以$u_1u_2u_3u_4u_5u_1$为轮圈的5-轮，则$f(G,4)=[f(G_1,4)-f(G_1\cup{u_1u_4,u_1u_3},4)] +[f(G_2,4)-f(G_2\cup {u_3u_1,u_3u_5},4)]+ [f(G_3,4)-f(G_3\cup {u_1u_4},4)]$，其中$G_1=(G-u)\circ{u_2,u_5}$, $G_2=(G-u)\circ{u_2,u_4}$, $G_3=(G-u)\circ{u_3,u_5}$，“$\circ$”表示收缩运算；进而讨论了使用公式证明四色猜想的应用：将四色猜想转化成研究一种特殊图类：4-色漏斗型伪唯一4-色极大平面图。

关键词：四色猜想, 极大平面图, 色多项式, 伪唯一4-色平面图, 4-色漏斗

基金资助：国家973规划项目(2013CB329600)，国家自然科学基金(61472012, 6152046, 6152012, 61572492, 61372191, 61472012)