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

doi:10.11999/JEIT160072

Abstract
Figure/Table
References (34)
Related Citation (3)

Download: PDF (734 KB)
Export: BibTeX | EndNote (RIS)

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.

Key words： Four-Color Conjecture Maximal planar graphs Chromatic polynomial Pseudo uniquely-4-colorable planar graphs 4-chromatic-funnel

Received: 15 January 2016 Published: 22 January 2016

PACS:

O157.5

Fund:

The National 973 Program of China (2013CB329600), The National Natural Science Foundation of China (61472012, 6152046, 6152012, 61572492, 61372191, 61472012)

Corresponding Authors: XU Jin E-mail: jxu@pku.edu.cn

About author:: XU Jin: Born in 1959, Professor. His main research interests include graph theory and combinatorial optimization, biocomputing, social networks and information security.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	XU Jin

Cite this article:

XU Jin. Theory on the Structure and Coloring of Maximal Planar Graphs (1)Recursion Formula of Chromatic Polynomial and FourColor Conjecture[J]. JEIT, 2016, 38(4): 763-779.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT160072 OR http://jeit.ie.ac.cn/EN/Y2016/V38/I4/763

[1]	JENSEN T R and TOFT B. Graph Coloring Problems[M]. New York: John Wiley & Sons, 1995: 48-49.
[2]	DÍAZ J, PETIT J, and SERNA M. A survey of graph layout problems[J]. ACM Computing Surveys, 2002, 34(3): 313-355.
[3]	BRODER A, KUMAR R, MAGHOUL F, et al. Graph structure in the Web[J]. Computer Networks, 2000, 33(1-6): 309-320.
[4]	许进, 李泽鹏, 朱恩强. 极大平面图的研究进展[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.
[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.