許 進(jìn)

?

極大平面圖的結(jié)構(gòu)與著色理論(1)色多項(xiàng)式遞推公式與四色猜想

許 進(jìn)*

(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)(北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100871)

該文給出了極大平面圖的色多項(xiàng)式遞推計(jì)算公式：若,是中輪心為，輪圈為的4-輪，則，其中,；若,是中為輪心，以為輪圈的5-輪，則，其中,，“”表示收縮運(yùn)算；進(jìn)而討論了使用公式證明四色猜想的應(yīng)用：將四色猜想轉(zhuǎn)化成研究一種特殊圖類：4-色漏斗型偽唯一4-色極大平面圖。

四色猜想；極大平面圖；色多項(xiàng)式；偽唯一4-色平面圖；4-色漏斗

1 引言

圖1 輪圖示例

如果一個(gè)圖能夠畫(huà)在平面上使得它的邊僅在頂點(diǎn)相交，則稱這個(gè)圖為平面圖。平面圖的這樣一種畫(huà)法稱為它的一個(gè)平面嵌入，本文所研究的平面圖均是指基于它的一個(gè)平面嵌入下的平面圖。對(duì)于一個(gè)平面圖，如果只要任何兩個(gè)不相鄰的頂點(diǎn)之間再加一條邊，其平面性一定被破壞，則稱該平面圖為極大平面圖。若一個(gè)平面圖的每個(gè)面(包括無(wú)窮面)都由3條邊界組成，則稱該平面圖為三角剖分圖。易證，極大平面圖和三角剖分圖是等價(jià)的。

無(wú)論是理論上還是應(yīng)用上，平面圖都是一類非常重要的圖類。理論上，著名的4-色猜想，唯一4-色平面圖猜想，9-色猜想，以及3-色問(wèn)題等[1]不僅在圖論領(lǐng)域，乃至整個(gè)數(shù)學(xué)界都具有重大影響；從應(yīng)用的角度來(lái)講，平面圖理論可直接應(yīng)用于電路布線[2]，信息科學(xué)[3]等領(lǐng)域。

由于著名的4-色猜想的研究對(duì)象可歸為極大平面圖，因此，100多年來(lái)，關(guān)于極大平面圖的研究吸引了眾多的學(xué)者，圍繞著4-色猜想，相繼研究了諸如度序列、構(gòu)造、著色特性、可遍歷性，生成運(yùn)算等諸多方面[4]。并且在研究過(guò)程中，提出了諸如唯一4-色極大平面圖猜想以及9-色猜想等，它們也逐漸構(gòu)成了極大平面圖著色理論的核心研究目標(biāo)。

在4-色猜想的研究過(guò)程中，從1879年KEMPE的“證明”[5]，到HEAWOOD的反例[6]，再到1976年由HAKEN與APPEL給出的“計(jì)算機(jī)證明”，主要集中在“尋找可約的不可避免集”這一種研究方法上。利用這種方法通過(guò)電子計(jì)算機(jī)找到了1936個(gè)可約的不可避免集，證明了四色猜想成立；1997年由ROBERTSON, SANDERS, SEYMOUR和THOMAS等人找出了633個(gè)可約構(gòu)形的不可避免集，簡(jiǎn)化了四色猜想的計(jì)算機(jī)證明。

“不可避免集”的研究起源于1904年WERNICKE的工作[12]；“可約構(gòu)形”是BIRKHOFF于1913年提出來(lái)的[13]。在利用“尋找可約的不可避免集”這種思想的證明過(guò)程中，德國(guó)數(shù)學(xué)家HEESCH做出了不可磨滅的貢獻(xiàn)，他發(fā)現(xiàn)了證明可約性的一種方法放電法[14]，并確信此方法可解決四色猜想，為1976年利用電子計(jì)算機(jī)求解四色猜想奠定了基礎(chǔ)。另外，還有不少學(xué)者在此方法上作出貢獻(xiàn)，諸如FRANKLIN, REYNOLDS[17], WINN[18], ORE和STEMPLE[19], MAYER[20]。

人是無(wú)法通過(guò)手工對(duì)不可避免集和可約構(gòu)形進(jìn)行驗(yàn)證的，因此，如何給出數(shù)學(xué)證明仍是一個(gè)尚待解決的數(shù)學(xué)難題。

除了基于“可約的不可避免集”的證明方法外，另一個(gè)具有影響的證明方法是基于假設(shè)：“每個(gè)3-正則3-連通的平面圖都有哈密頓圈”的條件給出的“證明”，該證明是由TAIT于1880年給出[21]。由于這個(gè)假設(shè)是錯(cuò)的，其證明自然是錯(cuò)的。這個(gè)錯(cuò)誤的假設(shè)是PETERSEN[22]發(fā)現(xiàn)的，但直到1946年，TUTTE才找到該證明的反例[23]。后來(lái)，GRINBERG[24]在1968年找到了一個(gè)必要條件，由此可產(chǎn)生很多3-正則3-連通的非HAMILTON平面圖。雖然TAIT的證明是錯(cuò)的，但TAIT的工作對(duì)于圖論的研究，特別是邊著色理論產(chǎn)生了深遠(yuǎn)的影響。用表示對(duì)標(biāo)定圖的頂點(diǎn)用種顏色進(jìn)行著色時(shí)具有的著色數(shù)目。顯然，當(dāng)時(shí)，即該圖沒(méi)法被著色時(shí)，；但當(dāng)，這種著色的數(shù)目肯定存在，即。對(duì)于任意一個(gè)平面圖，當(dāng)時(shí)，若能夠證明，則就相當(dāng)于證明了四色猜想！這就是BIRKHOFF在1912年提出用來(lái)證明四色猜想的一種方法[25,26]。后來(lái)發(fā)現(xiàn)，是一個(gè)關(guān)于的多項(xiàng)式，故稱為圖的色多項(xiàng)式。目前，圖的色多項(xiàng)式已經(jīng)成為了圖論學(xué)科中一個(gè)很有魅力的獨(dú)立分支[27]。遺憾的是，BIRKHOFF的愿望至今尚未實(shí)現(xiàn)。對(duì)色多項(xiàng)式的研究引起了眾多學(xué)者的極大興趣。關(guān)于這方面研究較為深入的文章與專著可參閱文獻(xiàn)[25-31]，其中文獻(xiàn)[28]的結(jié)果最為誘人，證明了：當(dāng)(其中)時(shí)，。此結(jié)果與四色猜想有點(diǎn)“擦肩而過(guò)”的遺憾，因?yàn)橹灰軌蜃C明，則四色猜想成立。

在計(jì)算給定圖的色多項(xiàng)式方面，一個(gè)最為基本的公式是所謂的縮邊遞推公式。

縮邊遞推公式[25]若圖是簡(jiǎn)單圖，則對(duì)圖的任何邊，都有

另外，本文作者在文獻(xiàn)[32,33]分別給出縮點(diǎn)遞推公式以及圖與補(bǔ)圖的色多項(xiàng)式等。

可能是因?yàn)門UTTE的工作很漂亮，以及TUTTE在學(xué)術(shù)界的地位，人們認(rèn)為以圖的色多項(xiàng)式為工具解決四色猜想似乎不可能，本文下述的工作重新“燃起”了利用圖的色多項(xiàng)式作為工具之一來(lái)證明四色猜想的希望。

2 色多項(xiàng)式的縮輪遞推公式

為方便，先給出如下2個(gè)引理：

引理1[26]對(duì)任何無(wú)自環(huán)的平面圖,是4-可著色的當(dāng)且僅當(dāng)

引理2[25,27]若圖是子圖與的并，且與的交為-階完全圖，則

圖2 一個(gè)含有4度頂點(diǎn)的極大平面圖

即

從而本定理獲證。

圖3 一個(gè)含有5度頂點(diǎn)的極大平面圖

由引理2，式(10)最后一個(gè)等號(hào)右端第1個(gè)圖的色多項(xiàng)式應(yīng)該為。因此，我們有

注意到式(13)等號(hào)右端第1個(gè)括號(hào)內(nèi)的第1個(gè)圖實(shí)際上就是圖；第2個(gè)括號(hào)內(nèi)的第1個(gè)圖實(shí)際上是；第3個(gè)括號(hào)內(nèi)的第1個(gè)子圖實(shí)際上是，從而本定理獲證。

3 定理2給出了證明四色猜想的一種思路

眾所周知，四色猜想的最終證明一般需采用數(shù)學(xué)歸納法，且按照最小度進(jìn)行分類。當(dāng)最小度為時(shí)，由歸納法容易證明，但當(dāng)時(shí)，至今數(shù)學(xué)方法尚未給出證明。下面，給出一種基于定理1和定理2的四色猜想證明思路：

關(guān)鍵是下面的情況3。

頂點(diǎn)數(shù)最少的最小度為5的極大平面圖是正20面體，如圖4(a)所示，具有12個(gè)頂點(diǎn)，它顯然是4-可著色的。不存在13階的最小度為5的極大平面圖。故對(duì)頂點(diǎn)數(shù)，且最小度為5的極大平面圖

第1種思路：顯然，由于

圖5 3個(gè)4-色漏斗型-偽唯一4-色極大平面圖

圖6 3個(gè)漏斗子圖的產(chǎn)生過(guò)程說(shuō)明示意圖

由此給出證明四色猜想的第2種思路：對(duì)于一個(gè)最小度為5的極大平面圖中的5-輪，對(duì)應(yīng)于,,的3個(gè)漏斗子圖,,至少有一個(gè)為非4-色漏斗。例如，我們視圖5(a)是由圖7中的5-輪按圖6所示的方法獲得的，容易證明，按圖6中所示的方法獲得的其余兩個(gè)極大平面圖不含4-色漏斗。

4 結(jié)束語(yǔ)

本文給出了求解極大平面圖的一種色多項(xiàng)式的遞推公式，由該公式發(fā)現(xiàn)：第一，證明四色猜想的兩種思路；第二，導(dǎo)出了一種將圖的著色與構(gòu)造相融合的構(gòu)造極大平面圖的方法擴(kuò)縮運(yùn)算系統(tǒng)，如圖5(a)就是通過(guò)所謂的擴(kuò)5-輪運(yùn)算獲得圖7中所示的極大平面圖，或者說(shuō)，圖7中所示的極大平面圖是通過(guò)縮5-輪運(yùn)算得到圖5(a)。極大平面圖的擴(kuò)縮運(yùn)算系統(tǒng)的詳細(xì)研究將在本系列文章的第2篇中給出。

圖7 可收縮成圖5中第1個(gè)圖的極大平面圖

致謝：本文在完成過(guò)程中相繼與我的5位圖論專業(yè)學(xué)生：朱恩強(qiáng)與李澤鵬博士后；劉小青與王宏宇博士生以及周洋洋碩士生等進(jìn)行了多次有益的討論，在此表示感謝。

[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]., 2002, 34(3): 313-355.

[3] BRODER A, KUMAR R, MAGHOUL F,. Graph structure in the Web[J]., 2000, 33(1-6): 309-320.

[4] 許進(jìn), 李澤鵬, 朱恩強(qiáng). 極大平面圖的研究進(jìn)展[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(7): 1680-1704.

XU Jin, LI Zepeng, and ZHU Enqiang. Research progress on the theory of maximal planar graphs[J]., 2015, 38(7): 1680-1704.

[5] KEMPE A B. On the geographical problem of the four colors [J]., 1879, 2(3): 193-200.

[6] HEAWOOD P J. Map colour theorem[J]., 1890, 24: 332-338.

[7] APPEL K and HAKEN W. The solution of the four-color map problem[J]., 1977, 237(4): 108-121.

[8] APPEL K and HAKEN W. Every planar map is four colorable, I: Discharging[J]., 1977, 21(3): 429-490.

[9] APPEL K, HAKEN W, and KOCH J. Every planar map is four-colorable, II: Reducibility[J]., 1977, 21(3): 491-567.

[10] ROBERTSON N, SANDERS D P, SEYMOUR P,. A new proof of the four colour theorem[J]., 1996, 2: 17-25.

[11] ROBERTSON N, SANDERS D P, SEYMOUR P D,. The four color theorem[J].,, 1997, 70(1): 2-44.

[13] BIRKHOFF G D. The reducibility of maps[J]., 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].,1922, 44(3): 225-236.

[16] FRANKLIN P. Note on the four color problem[J]., 1938, 16: 172-184.

[17] REYNOLDS C. On the problem of coloring maps in four colors[J]., 1926-27, 28(1-4): 477-492.

[18] WINN C E. On the minimum number of polygons in an irreducible map[J]., 1940, 62(1): 406-416.

[19] ORE O and STEMPLE J. Numerical calculations on the four-color problem[J]., 1970, 8(1): 65-78.

[20] MAYER J. Une propriètè des graphes minimaux dans le problμeme des quatre couleurs[J].,, 1978, 260: 291-295.

[21] TAIT P G. Remarks on the colouring of maps[J]., 1880, 10: 501-516.

[22] PETERSEN J. Surle théorème de Tait[J]., 1898, 5: 225-227.

[23] TUTTE W T. On Hamiltonian circuits[J]., 1946, 21: 98-101.

[24] GRINBERG E J. Plane homogeneous graphs of degree three without Hamiltonian circuits[J]., 1968, 5: 51-58.

[25] BIRKHOFF G D. A determinantal formula for the number of ways of coloring a map[J]., 1912, 14: 42-46.

[26] BIRKHOFF G D and LEWIS D. Chromatic polynomials[J].

, 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]., 1970, 9(3): 289-296.

[29] TUTTE W T. Chromatic sums for planar triangulations, V: Special equations[J]., 1974, 26: 893-907.

[30] READ R C. An introduction to chromatic polynomials[J]., 1968, 4(1): 52-71.

[31] WHITNEY H. On the coloring of graphs[J]., 1932, 33(4): 688-718.

[32] XU Jin. Recursive formula for calculating the chromatic polynomial of a graph by vertex deletion[J]., 2004, 24(4): 577-582.

[33] XU Jin and LIU Z. The chromatic polynomial between graph and its complementAbout Akiyama and Hararys,open problem[J]., 1995, 11: 337-345.

[34] ZYKOV A A. On some properties of linear complexes[J]., 1949, 24(66): 163-188 (in Russian);, 1952, 79.

許 進(jìn)： 男，1959年生，教授，主要研究領(lǐng)域?yàn)閳D論與組合優(yōu)化、生物計(jì)算機(jī)、社交網(wǎng)絡(luò)與信息安全等.

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

Theory on the Structure and Coloring of Maximal Planar Graphs(1)Recursion Formulae of Chromatic Polynomial and Four-Color Conjecture

XU Jin

(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)(Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China)

In this paper, two recursion formulae of chromatic polynomial of a maximal planar graphare obtained: when, letbe a 4-wheel ofwith wheel-centerand wheel-cycle, then; when, leta 5-wheel ofwith wheel-centerand wheel-cycle, then,,, where“”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

O157.5

A

1009-5896(2016)04-0763-17

10.11999/JEIT160072

2016-01-15；改回日期：2016-01-20；網(wǎng)絡(luò)出版：2016-01-22

許進(jìn) jxu@pku.edu.cn

國(guó)家973規(guī)劃項(xiàng)目(2013CB329600)，國(guó)家自然科學(xué)基金(61472012, 6152046, 6152012, 61572492, 61372191, 61472012)