一種特殊的多米諾擴縮運算

劉小青 許 進

?

一種特殊的多米諾擴縮運算

劉小青 許 進*

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

該文提出一種稱為334擴縮運算的多米諾擴縮運算。使用該運算構造了一類特殊的極大平面圖——334-型極大平面圖，證明了該類圖均為樹型2-色不變圈著色，且每個-階334-型極大平面圖恰有個2-色不變圈著色及個樹著色。證明了該運算可用于構造純樹著色極大平面圖，并提出猜想：若極大平面圖是純樹(純圈，混合)著色，則對實施334擴(縮)輪運算后，所得之圖仍是純樹(純圈，混合)著色。

半封漏斗；樹型2-色不變圈著色；純樹著色；334擴輪運算

1 引言

文獻[6,7]對平面圖的著色類型進行了研究，將著色分為樹著色和圈著色，依據著色類型將4-色平面圖分為3類：純樹著色型、純圈著色型和混合著色型，并提出了純樹著色猜想“一個平面圖是純樹著色圖當且僅當它是正二十面體或啞鈴極大平面圖”，若該猜想成立，則著名的已有43年歷史的唯一4-色平面圖猜想成立。文獻[13]定義了一類特殊的圈著色2-色不變圈著色，在此基礎上，將4-色非Kempe平面圖的Kempe等價類分為樹型，圈型和循環圈型，這也是非Kempe平面圖存在的根源。若一個-色圖的都有-著色構成一個Kempe等價類，則稱該圖為Kempe圖。

本文給出了一種構造具有相同著色類型的極大平面圖類的方法，包含334擴輪運算和334縮輪運算。具體安排如下：第2節給出了334擴輪運算及334縮輪運算的定義；第3節基于334擴縮運算研究了一類樹型2-色不變圈著色極大平面圖334-型極大平面圖的基本性質；第4節討論了334-型極大平面圖的著色性質；第5節給出了用334擴輪運算構造純樹著色極大平面圖的方法。

文中未給出的相關定義、記號與理論參見文獻[6,13-15]。

圖1 漏斗與45-型半封漏斗子圖

2 334擴縮運算

把圖1(a)中所示的圖稱為漏斗，其中度數為1的頂點稱為漏頂；度數為3的頂點稱為漏腰；2個度數為2的頂點稱為漏底。若一個圖的頂點導出子圖是漏斗，則該子圖稱為漏斗子圖。334擴縮運算本質上是一種多米諾擴縮運算[14]，其中，334擴輪運算包含2次擴3-輪運算以及一次擴4-輪運算；334縮輪運算包含2次縮3-輪運算以及一次縮4-輪運算。設是一個極大平面圖，圖是一個標號如圖1(b)所示的半封漏斗。若是的一個子圖，且，，則稱是的一個45-型半封漏斗子圖，簡稱為45-型子圖。

334擴輪運算的對象圖是極大平面圖中的45-型子圖。334擴輪運算，記作，是指按照如下步驟，將的一個45-型子圖(如圖1(b)所示)變成圖2(a)~2(d)中最右邊所示構形的過程：

圖2 選擇不同漏腰和漏底的334擴輪運算過程示意圖

(2)在圖2(a)與圖2(d)中，2個最右邊構形的區別僅是構形的內部頂點標號不同，若對一個極大平面圖的同一個45-型子圖分別實施如圖2(a)和圖2(d)所示過程的334擴輪運算，則得到2個相同的極大平面圖，故視這2個構形是相同的；同理，圖2(b)與圖2(c)中2個最右邊的構形是相同的。

圖3(a)，圖3(d)，圖3(e)，圖3(h)中最右邊構形的區別僅是構形的頂點標號方式不同，對一個極大平面圖的同一個334子圖分別實施如圖3(a)，圖3(d)，圖3(e)，圖3(h)所示過程的334縮輪運算，則得到4個相同的極大平面圖，故視圖3(a)，圖3(d)，圖3(e)，圖3(h)中最右邊的構形是相同的；同理，圖3(b)，圖 3(c)，圖3(f)，圖3(g)中最右邊的構形是相同的。

圖3 選擇不同被收縮點對的334縮輪運算過程示意圖

3 334-型極大平面圖

3.1334-型極大平面圖及構造

圖4所示的圖是階數最小的最小度為4且含45-型子圖的極大平面圖，稱為8-階334-型極大平面圖，記作。

3.2 334-型極大平面圖的基本性質

由定理2可推出下述結論：

證明 由前面討論知，任意334子圖僅有一個與之不相同的334子圖。

圖4 8-階334-型極大平面圖 圖5 2個12-階334-型極大平面圖

若將圖5(a)中上方的334子圖替換為與之不相同的334子圖，如圖6(a)所示，則得到一個與圖5(b)同構的圖；若將圖5(a)中下方的334子圖替換為與之不相同的334子圖，如圖6(b)所示，則得到一個與圖5(b)同構的圖。若將圖5(b)中的任意一個334子圖替換為與之不相同的334子圖，則得到與圖5(a)同構的圖。故時結論成立。

圖6 定理3證明示意圖

由推論1和定理3，可直接推出下述結論：

定理4 每個334-型極大平面圖恰有4個4度頂點。

8-階334-型極大平面圖為如圖4所示的圖，其度序列為44445555，結論成立。12-階334-型極大平面圖共有2個，分別如圖5(a)，圖5(b)所示，它們均恰含4個4度頂點，結論成立。

圖7 2個不相同的334子圖　　　　　　圖8 2個不相同的45-型子圖

4 334-型極大平面圖著色性質

在擴4-輪運算過程中，對象子圖2-長路的內點被劃開成為2個頂點，如圖9所示，將該內點稱為擴點，由劃開產生的2個頂點稱為擴點的拷貝頂點。類似，把擴5-輪運算對象子圖的漏腰稱為擴點，擴點被劃開后產生的2個頂點稱為擴點的拷貝頂點。

圖9 擴縮4-輪運算的示意圖

圖10 的所有著色

定理5 每個334-型極大平面圖均是樹型2-色不變圈著色。

圖11 的所有著色

圖12 的所有著色

證畢

5 構造純樹著色極大平面圖

利用334擴輪運算，除了構造334-型極大平面圖，還可以構造其它非常重要的圖類，例如，純樹著色極大平面圖。7至11階最小度的極大平面圖共有54個[14]，其中純樹著色的圖只有1個[6,7]，記作，如圖13(a)所示。共有3個45-型子圖。對其中的任意一個45-型子圖實施334擴輪運算，均得到如圖13(b)所示的13-階純樹著色極大平面圖，記為。

由定理5知，從一個最小度為4的8-階樹型2-色不變圈著色極大平面圖出發，實施任意次數的334擴輪運算后，所得之圖均是樹型2-色不變圈著色的；再由定理7知，從一個最小度為4的9-階純樹著色極大平面圖出發，實施任意次數的334擴輪運算后，所得之圖也都是純樹著色的?；谶@些結論，我們進一步提出如下猜想：

圖13 和

6 結束語

本文給出了一種稱為334擴縮運算的擴縮運算，它能夠構造具有相同著色類型的4-色極大平面圖。在后續工作中，我們將對文中給出的猜想予以論證，并進一步研究不同著色類型圖所具有的特殊性質。

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] 許進. 極大平面圖的結構與著色理論(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.

[7] XU J, LI Z P, and ZHU E Q. On purely tree-colorable planar graphs[J]., 2016, 116(8): 532-536. doi: 10.1016/j.ipl.2016.03.011.

[8] GREENWELL D and KRONK H V. Uniquely line-colorable graphs[J]., 1973, 16(4): 525-529. doi: 10.4153/CMB-1973-086-2.

[9] THOMASON A G. Hamiltonian cycles and uniquely edge colourable graphs[J]., 1978, 3: 259-268. doi:10.1016/S0167-5060(08)70511-9.

[10] FIORINI S and WILSON R J. Edge colouring of graphs[J]., 1977, 23(1): 237-239.

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

[12] TOMMY R J and BJARNE T. Graph Coloring Problems[M].New York: USA, John Wiley & Sons, Inc., 1994: 1-295.

XU J. Theory on structure and coloring of maximal planar graphs (4):-operations and Kempe equivalent classes[J].&, 2016, 38(7): 1557-1585. doi: 10.11999/JEIT160483.

[14] 許進. 極大平面圖的結構與著色理論(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/JEIT 160224.

[15] BONDY J A and MURTY U S R. Graph Theory[M]. New York: USA, Springer, 2008: 8-200.

劉小青： 女，1986年生，博士生，研究方向為圖論與組合優化.

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

Special Type of Domino Extending-contracting Operations

LIU Xiaoqing XU Jin

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

In this paper, a new domino extending-contracting operation, called 334 extending-contracting operation, is put forward, on the basis of which, it is proposed to construct a particular kind of graphs, i.e., 334-type maximal planar graphs, and proved that all those graphs are tree-type and 2-chromatic cycle-unchanged colored and every 334-type maximal planar graphs of orderhas exactly2-chromatic cycled-unchanged colorings andtree-colorings. Additionally, it is proved that an infinite family of purely tree-colored graphs can be generated by implementing a series of 334 extending-wheel operations, and conjectured that if a maximal planar graphis purely tree-colored (purely cycle-colored or impure-colored), then the graph obtained by implementing one 334 extending-wheel (contracting-wheel) operation onis still purely tree-colored (purely cycle-colored or impure-colored).

Semi-funnels; Tree-type and 2-chromatic cycle-unchanged colored; Purely tree-colored; 334 extending- wheel operations

O157.5

A

1009-5896(2017)01-0221-10

10.11999/JEIT160886

2016-08-29；改回日期：2016-12-06；

2016-12-14

許進 jxu@pku.edu.cn

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

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