極大平面圖的結構與著色理論 (4)-運算與Kempe等價類

許 進

?

極大平面圖的結構與著色理論 (4)-運算與Kempe等價類

許 進*

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

設是一個-色圖，若的所有-著色是Kempe等價的，則稱為Kempe圖。表征色數的Kempe圖特征是一尚待解決難題。該文對極大平面圖的Kempe等價性進行了研究，其主要貢獻是：(1)發現導致兩個4-著色是Kempe等價的關鍵子圖為2-色耳，故對2-色耳的特征進行了深入研究；(2)引入-特征圖，清晰地刻畫了一個圖中所有4-著色之間的關聯關系，并深入研究了-特征圖的性質；(3)揭示了4-色非Kempe極大平面圖的Kempe等價類可分為樹型，圈型和循環圈型，并指出這3種類型可同時存在于一個極大平面圖的4-著色集中；(4)研究了Kempe極大平面圖特征，給出了該類圖的多米諾遞推構造法，以及兩個Kempe極大平面圖猜想。

Kempe極大平面圖；Kempe變換；-運算；Kempe等價類；-特征圖；2-色耳

1 引言

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

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

在極大平面圖的著色性質與結構方面，一項很重要的工作是Kempe變換與Kempe等價類。Kempe變換是指在一個著色圖中，將某個2-色導出子圖的某個連通分支上的顏色互換，其余頂點的著色不變的一種顏色變換方法。本文所定義的-運算是指在4-著色下的包含一次或多次Kempe變換的運算(詳見第3節)。-運算是一種導色運算：從中的一個4-著色導出的另一個4-著色。

Kempe變換始于1879年Kempe的工作[5]。自Kempe之后，首先對Kempe等價類進行系統研究的是Fisk，他在1977年文獻[6]中證明了：當一個極大平面圖的頂點度數均為偶數時，其所有4-著色構成一個Kempe等價類；1978年，Meyniel證明了：任一平面圖的所有5-著色構成一個Kempe等價類[7]；1981年，Vergnas與Meyniel證明了：不可收縮至的任一簡單圖的所有5-著色是一個Kempe等價類[8]；2007年，Mohar證明了：每個色數小于的平面圖，其所有-著色是Kempe等價的[9]，并提出了下列猜想：

2015年，Feghali等人[10]證明了猜想1在時，除或三角柱外，立方體圖的所有3-著色是Kempe等價的；我們證明了當時，猜想1成立1)；當時，此猜想尚待解決。

2008年，Cereceda等人[11]對的-色特征圖進行了研究，其中，的頂點集為的所有-著色構成的集合，兩個-著色相連邊當且僅當它們在中僅有一個頂點著不同顏色，并證明了：當的色數時，不連通；當時，可能連通，也可能不連通。

類似于頂點著色，一些學者對邊著色的Kempe變換與Kempe等價類進行了研究，如Mcdonald等人[12]，Sarah等人[13]等。

有關Kempe變換與Kempe等價類的圖算法復雜度的研究進展可參見文獻[14-24]。

本系列文章意在建立極大平面圖著色運算系統，該系統有兩種導色運算：一種是-運算，另一種是-運算，也稱為偽邊導色法(另行文)。而在一個極大平面圖中，-運算一般不能從一個4-著色導出所有4-著色，或所需的4-著色，但-運算可從中的一個4-著色導出所有的4-著色，或所需4-著色。

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

把圖1中所示的圖稱為漏斗，其中度數為1的頂點稱為漏頂；度數為3的頂點稱為漏腰；兩個度數為2的頂點稱為漏底。若一個圖的頂點導出子圖是漏斗，則該子圖稱為漏斗子圖。更詳細論述見本系列文章(2)[25]。

圖1 漏斗

文中未給出的相關定義、記號與理論參見文獻[25-27]。

2 2-色耳

本節先對2-色圈給予描述與分類，在此基礎上給出2-色耳的定義與結構等。2-色耳是可連續施行-運算的根源。

2.1 2-色圈相關定義

圖2 弦圈、弦路圈與基本圈

圖3兩個2-色圈相關的情況

2.2 2-色耳的相關定義與性質

圖4 耳朵、同根耳、同源耳說明示意圖

證畢

圖5 成圈的同色耳結構示意圖，其中實線表示

文獻[26]中引入了樹著色與圈著色的概念，為方便，在此重述如下。設是一個4-色極大平面圖，,為顏色集。若，使得中含圈，則稱為圈著色，并稱為可圈著色的；反之，若,中均無圈，則稱為圖的樹著色，并稱為可樹著色的；若是可樹著色，但非可圈著色，則稱為純樹著色的；若是可圈著色，但非可樹著色，則稱為純圈著色的；若既是可圈著色，又是可樹著色，則稱為混合型著色的。由圈著色與樹著色的定義，對任一4-色極大平面圖，可將中的著色分為兩類：圈著色與樹著色。

圖6 -運算示例

圖7 圖6中所示圖的-特征圖

對于階數不超過11的所有極大平面圖，樹著色的數目約占2%[26]。故我們推測對最小度的極大平面圖集，樹著色數相比圈著色數來說非常少，因此，給定4-色極大平面圖的一個圈著色，很有可能通過-運算將中的其它著色推導出來。

圖8 不相交的情況

如下2種情況給予證明：

圖9 相交的情況

基于上述兩種情況，本定理獲證。

圖10 定理6證明示意圖

4 非Kempe圖的Kempe等價類類型

4.1 樹型Kempe等價類

由此推出定理8：

4.2 圈型Kempe等價類

圖12中分別給出了兩個都含2個2-色不變圈的極大平面圖，其中第1個圖中的2個2-色不變圈有兩個公共頂點。圖12(a)-圖12(j)給出了該圖的所有4-著色，且在圖12(k)給出了它的-特征圖。圖12(l)給出了含不相交的2個2-色不變圈(用粗線標記)的極大平面圖。

4.3 循環圈型Kempe等價類

圖13 圈型及循環型圈型Kempe等價類的兩個例子

純圈型，即含1個或多個2-色不變圈，如圖11，圖12所示的圖；

圖11 只含有一個2-色不變圈的圈型極大平面圖

圖12 含2個2-色不變圈的圈型極大平面圖

混合型，即既含2-色不變圈型，又含循環圈型，如圖13(a)；

純循環圈型，即只含1個或多個循環2-色圈，如圖13(c)中所給出的4-著色，它同時含2個循環圈型。

注1 有些圖在不同著色下含相同的某2-色圈，但這些著色并不屬于同一Kempe等價類。

注2 由上述給出3種Kempe等價類可知，在一個給定的最小度的極大平面圖中，中可能存在1~3種Kempe等價類，且可能存在多個同種類型的Kempe等價類。如正20面體含有10個樹型等價類。

5 Kempe圖

5.1 Kempe圖猜想

此猜想與唯一4-色極大平面圖猜想息息相關。若唯一4-色極大平面圖猜想成立，即每個唯一4-色極大平面圖是遞歸極大平面圖[26]，則最小度的4-色極大平面圖至少有2種不同的4-著色。若是樹型，由于樹著色不能通過-運算到達的其它4-著色，因此一定不是Kempe圖。

即使猜想3成立，也不能僅從Kempe圖所含等價類的類型來確定Kempe圖的特征。為深入研究Kempe圖的特征，我們提出了多米諾遞推構造法。

5.2 Kempe圖的構造

由本系列文章(2)[25]知：一個最小度的-階極大平面圖，其祖先圖集中必含-階，或-階最小度的極大平面圖。換言之，中至少存在圖14中的5個基本多米諾構形之一。為方便，本系列文章將5個基本多米諾構形分別標記為,,,,，如圖14所示。

圖14 5個基本多米諾構形

關于Kempe極大平面圖更為深入的研究將在后續文章中給出，其中包括定理11的詳細論證，猜想4的論證，以及與的關系等的研究。

6 結束語

眾所周知，表征Kempe圖的特征一直是圖著色理論與算法研究中的難點與熱點問題。目前雖然在此領域中發表了不少學術論文，但是給出一般色數為的Kempe圖的充分必要條件仍很困難，故目前學界主要對一些特殊圖類的Kempe等價類展開研究，如正則圖等。本系列文章主要對另一類圖——極大平面圖的Kempe等價類展開了研究。

本文的主要貢獻是：(1)發現了導致兩個4-著色是Kempe等價的關鍵子圖為2-色耳，故對2-色耳的特征進行了深入研究；(2) 引入-特征圖，清晰地刻畫了圖中所有著色之間的關聯關系，并對-特征圖的性質進行了深入的研究；(3)揭示了非Kempe圖的Kempe等價類可分為樹型，圈型和循環圈型，并指出這3種類型可同時存在于一個極大平面圖的4-著色集中；(4)研究了Kempe圖的特征，給出了Kempe圖的多米諾遞推構造法，并猜想與是Kempe圖的充分必要條件是在圖中可4-色漏斗子圖的個數。

在后續文章中將對3類非Kempe圖的結構與特征進行深入研究，特別，將給出Kempe極大平面圖的充分必要條件。

致謝 本文在完成過程中，與姚兵教授、陳祥恩教授以及吳建良教授，以及我的6位圖論專業學生：王宏宇(博士生)，劉小青(博士生)，朱恩強(博士后)，李澤鵬(博士后)，周洋洋(碩士生)，以及趙棟楊(碩士生)等進行了多次有益討論，在此表示感謝。最后，特別感謝北京大學何新貴院士、余道衡教授對本文的審閱，以及對作者的鼓勵、鞭策與支持。

[1] JENSEN T R and TOFT B. Graph coloring problems[J].-, 1995, 113(2): 29-59. doi: 10.1002/ 9781118032497.ch2.

[2] DIAZ J, PETIT J, and SERNA M. A survey of graph layout problems[J]., 2002, 34(3): 313-356. doi: 10.1145/568522.568523.

[3] BRODER A, KUMAR R, MAGHOUL F,Graph structure in the web[J]., 2000, 33(1/6): 309-320. doi: 10.1016/S1389-1286(00)00083-9.

[4] 許進, 李澤鵬, 朱恩強. 極大平面圖理論研究進展[J]. 計算機學報, 2015, 38(8): 1680-1704. doi: 10. 11897/SP.J.1016.2015. 01680.

XU J, LI Z P, and ZHU E Q. Research progress on the theory of maximal planar graphs[J]., 2015, 38(8): 1680-1704. doi: 10.11897/SP.J.1016.2015. 01680.

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

[6] FISK S. Geometric coloring theory[J].,1977, 24(3): 298-340. doi: 10.1016/0001- 8708(77)90061-5.

[7] MEYNIEL H. Les 5-colorations d'un graphe planaire Forment une classe de commutation unique[J]., 1978, 24(3): 251-257. doi: 10.1016/0095-8956(78)90042-4.

[8] VERGNAS M L and MEYNIEL H. Kempe classes and the Hadwiger conjecture[J]., 1981, 31(1): 95-104. doi: 10.1016/S0095- 8956(81)80014-7.

[9] MOHAR B. Kempe Equivalence of Colorings[M]. Graph Theory in Paris, Birkh?user Basel, 2006: 287-297. doi: 10.1007/978-3-7643-7400-6_22.

[10] FEGHALI C, JOHNSON M, and PAULUSMA D. Kempe equivalence of colourings of cubic graphs[J]., 2015, 49: 243-249. doi: 10.1016/j. endm.2015.06.034.

[11] CERECEDA L, HEUVEL J V D, and JOHNSON M. Connectedness of the graph of vertex-colourings[J]., 2008, 308(5/6): 913-919. doi: 10.1016/j.disc. 2007.07.028.

[12] MCDONALD J, MOHAR B, and SCHEIDE D. Kempe equivalence of edge-colorings in subcubic and subquartic graphs[J]., 2012, 70(2): 226-239. doi: 10.1002/jgt.20613.

[13] BELCASTRO S M and HAAS R. Counting edge-Kempe- equivalence classes for 3-edge-colored cubic graphs[J]., 2014, 325(13): 77-84. doi: 10.1016/j. disc.2014.02.014.

[14] FIOL M A and VILALTELLA J. A simple and fast heuristic algorithm for edge-coloring of graphs[J]., 2013, 10(3): 263-272.

[15] EFTHYMIOU C and SPIRAKIS P G. Random sampling of colourings of sparse random graphs with a constant number of colours[J]., 2008, 407(1/3): 134-154. doi: 10.1016/j.tcs.2008.05.008.

[16] DYER M, FLAXMAN A D, FRIEZE A M,. Randomly coloring sparse random graphs with fewer colors than the maximum degree[J]., 2006, 29(4): 450-465. doi: 10.1002 /rsa.20129.

[17] HAYES T P and VIGODA E. A non-Markovian coupling for randomly sampling colorings[C]. 44th Annual Symposium on Foundations of Computer Science, 2003: 618-627. doi: 10.1109/SFCS.2003.1238234.

[18] LUCZAK T and VIGODA E. Torpid mixing of the Wang- Swendsen-Kotecky algorithm for sampling colorings[J]., 2005, 3(1): 92-100. doi: 10.1016/j.jda.2004.05.002.

[19] MORGENSTERN C A and SHAPIRO H D. Heuristics for rapidly four-coloring large planar graphs[J]., 1991, 6(1): 869-891. doi: 10.1007/BF01759077.

[20] SIBLEY T and WAGON S. Rhombic penrose tilings can be 3-colored[J]., 2000, 107(3): 251-253. doi: 10.2307/2589317.

[21] VIGOD E. Improved bounds for sampling colorings[C]. 40th Annual Symposium on Foundations of Computer Science, New York, 1999: 51-59. doi: 10.1109/SFFCS.1999.814577.

[22] FRIEZE A and VIGODA E. A survey on the use of markov chains to randomly sample colourings[C]. In Combinatorics, Complexity, and Chance. Oxford Lecture Ser. Math. Appl. 34 53-71. Oxford Univ. Press, Oxford. MR2314561doi: 10.1093/acprof:oso/9780198571278.003.0004.

[23] HAYES T P and VIGODA E. Coupling with the stationary distribution and improved sampling for colorings and independent sets[J]., 2006, 16(3): 1297-1318. doi: 10.1214/105051606000000330.

[24] BALASUBRAMANIAN R and SUBRAMANIAN C R. On sampling colorings of bipartite graphs[J]., 2006, 8(1): 17-30.

[25] 許進. 極大平面圖的結構與著色理論(2): 多米諾構形與擴縮運算[J]. 電子與信息學報, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.

XU J. Theory on structure and coloring of maximal planar graphs (2): Domino configurations and extending- contracting operations[J].&, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.

[26] 許進. 極大平面圖的結構與著色理論(3): 純樹著色與唯一4-色平面圖猜想[J]. 電子與信息學報, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.

XU J. Theory on structure and coloring of maximal planar graphs (3): Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures[J].&, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.

[27] BONDY J A and MURTY U S R. Graph Theory[M]. Springer, 2008: 6-58.

Theory on Structure and Coloring of Maximal Planar Graphs (4)-Operations and Kempe Equivalent Classes

XU Jin

(,,100871,),(,,100871,)

Letbe a-chromatic graph.is called a Kempe graph if all-colorings ofare Kempe equivalent. It is an unsolved and hard problem to characterize the properties of Kempe graphs with chromatic number. The Kempe equivalence of maximal planar graphs is addressed in this paper. Our contributions are as follows: (1) Observe and study a class of subgraphs, called 2-chromatic ears, which play a critical role in guaranteeing the Kempe equivalence between two 4-colorings; (2) Introduce and explore the properties of-characteristic graphs, which clearly characterize the relations of all 4-colorings of a graph; (3) Divide the Kempe equivalent classes of non-Kempe 4-chromatic maximal planar graphs into three classes, tree-type, cycle-type, and circular-cycle-type, and point out that all these three classes can exist simultaneously in the set of 4-colorings of one maximal planar graph; (4) Study the characteristics of Kempe maximal planar graphs, introduce a recursive domino method to construct such graphs, and propose two conjectures.

Kempe maximal planar graph, Kempe transformation,-operation, Kempe equivalent class,-characteristic graph, 2-chromatic ear

O157.5

A

1009-5896(2016)07-1557-29

10.11999/JEIT160483

2016-05-11；改回日期：2016-05-30；網絡出版：2016-06-02

：許進 jxu@pku.edu.cn

國家973計劃項目(2013CB329600)，國家自然科學基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

The National 973 Program of China (2013CB 329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

1)LIU Xiaoqing, XU Jin, submitted to Discrete Mathematics.

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