極大平面圖的結構與著色理論(1)色多項式遞推公式與四色猜想

許 進

?

極大平面圖的結構與著色理論(1)色多項式遞推公式與四色猜想

許 進*

(北京大學信息科學技術學院 北京 100871)(北京大學高可信軟件技術教育部重點實驗室 北京 100871)

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

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

1 引言

圖1 輪圖示例

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

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

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

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

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

人是無法通過手工對不可避免集和可約構形進行驗證的，因此，如何給出數學證明仍是一個尚待解決的數學難題。

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

在計算給定圖的色多項式方面，一個最為基本的公式是所謂的縮邊遞推公式。

縮邊遞推公式[25]若圖是簡單圖，則對圖的任何邊，都有

另外，本文作者在文獻[32,33]分別給出縮點遞推公式以及圖與補圖的色多項式等。

可能是因為TUTTE的工作很漂亮，以及TUTTE在學術界的地位，人們認為以圖的色多項式為工具解決四色猜想似乎不可能，本文下述的工作重新“燃起”了利用圖的色多項式作為工具之一來證明四色猜想的希望。

2 色多項式的縮輪遞推公式

為方便，先給出如下2個引理：

引理1[26]對任何無自環的平面圖,是4-可著色的當且僅當

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

圖2 一個含有4度頂點的極大平面圖

即

從而本定理獲證。

圖3 一個含有5度頂點的極大平面圖

由引理2，式(10)最后一個等號右端第1個圖的色多項式應該為。因此，我們有

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

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

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

關鍵是下面的情況3。

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

第1種思路：顯然，由于

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

圖6 3個漏斗子圖的產生過程說明示意圖

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

4 結束語

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

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

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

[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]. 計算機學報, 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.

許 進： 男，1959年生，教授，主要研究領域為圖論與組合優化、生物計算機、社交網絡與信息安全等.

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；網絡出版：2016-01-22

許進 jxu@pku.edu.cn

國家973規劃項目(2013CB329600)，國家自然科學基金(61472012, 6152046, 6152012, 61572492, 61372191, 61472012)