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

许进

doi:10.11999/JEIT160072

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

doi: 10.11999/JEIT160072

许进¹

基金项目:

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

计量
- 文章访问数: 2551
- HTML全文浏览量: 104
- PDF下载量: 1012
- 被引次数: 0
出版历程
- 收稿日期: 2016-01-15
- 修回日期: 2016-01-18
- 刊出日期: 2016-04-19

Theory on the Structure and Coloring of Maximal Planar Graphs (1)Recursion Formula of Chromatic Polynomial and FourColor Conjecture

XU Jin¹

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$”表示收缩运算；进而讨论了使用公式证明四色猜想的应用：将四色猜想转化成研究一种特殊图类：4-色漏斗型伪唯一4-色极大平面图。
- 四色猜想 /
- 极大平面图 /
- 色多项式 /
- 伪唯一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.
- Four-Color Conjecture /
- Maximal planar graphs /
- Chromatic polynomial /
- Pseudo uniquely-4-colorable planar graphs /
- 4-chromatic-funnel

HTML全文

参考文献(35)

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]. 计算机学报, 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.

施引文献

资源附件(0)

访问统计