不包含｛4，8，9｝－圈平面圖結構的性質

方冬云

（莆田學院 數學系，福建 莆田 351100）

1 基本術語及符號［1］

圖論一個偶對G＝（V，E）來定義圖，其中V表示頂點的集合，E表示邊的集合，如果圖G中邊的兩個頂點是無序的，則稱圖G為無向圖。一般圖G＝（V，E）的頂點數用｜V｜表示，邊的數目用｜E｜表示，如果｜V｜和｜E｜都是有限的，則稱圖G是有限無向圖，如果圖G既沒有環也沒有兩條連桿連接同一對頂點，則稱圖是簡單圖，文中所研究的圖均指的是有限簡單無向圖。有限簡單無向圖G中的頂點u和v，若邊e＝uv∈E（G），則稱u和v相鄰，也稱u和v是e的端點，u和v分別與e相關聯，則稱u為圖G中的任一頂點，與頂點u關聯的邊數稱為u的度數，記作dG（u）。

如果有限簡單無向圖G能畫在曲面上，且除端點處之外任何兩條邊均不相交，則稱圖G被嵌入曲面上，如果圖G可以被嵌入在平面上，稱為是可平面圖，已經被嵌入在平面上的圖稱為平面有限簡單無向圖。設u和v是圖的頂點，圖G的一條u－v途徑（鏈）是有限非空的頂點和邊交替序列W＝u0e1u2e3…un－1enun（u＝u0，v＝vn），其中與邊ei（1≤i≤n）相鄰的兩頂點ui－1和ui正好是ei的兩個端點，如果w上的頂點互不同的途徑稱為路記作Pi，u0，ui分別為Pi的起點和終點，起點和終點相同的路稱為圈。

圖G的一個k－染色是一個映射φ：V→｛1，…，k｝，使得φ（u）≠φ（v），其中uv∈E。這樣的映射稱圖G為k－可染。如果G有一個k－染色，令H是圖G的一個點導出子圖，φ是H 的一個k－染色，若G有一個k－染色φ，且滿足φ在H 上的限制正好是φ，則稱φ是φ在圖G上的一個延拓，或稱φ可以延拓到圖G上。

令C是圖G的一個圈，分別記圈C內部和外部的點集為int（C）和ext（C）。顯然，Int（C）＝G－ext（C）和Ext（C）＝G－int（C）是圖G的兩個點導出子圖。連接一個圈上不相鄰兩點間的連線稱為弦，注意，在C內部的C的弦屬于Ext（C）。若恒有int（C）≠Φ且ext（C）≠Φ，則稱C為分離圈。否則稱C是一個非分離的圈。

2 一些平面圖研究成果的簡介

平面有限簡單無向圖（簡稱平面圖）的點染色問題起源于著名的四色猜想，接著，人們試著對4－可選擇的平面圖作了一些特征刻畫，且關于2－可選擇這樣的問題，Erdos［2］等人已經做了特征化的論述，因此，許多學者對平面圖3－可染（可選擇）問題做了一系列的討論與研究：

存在一個常數k＊，使得不包含｛4，5，…，K＊｝－圈的平面圖是3－可染的［3］；不包含｛4，5，…，9｝圈的平面圖是3－可染的［4］；每個不包含｛4，6，8.9｝－圈的平面圖是3－可選擇的［5］；每個不包含｛4，6，8｝－圈的平面圖是3－可染的［6］；每個不包含｛4，7，9｝－圈的平面圖是3－可染的［7］；每個不包含｛4，6，9｝－圈的平面圖是3－可染的［8］；根據這些研究的成果，進一步分析不包含｛4，8，9｝－圈的平面圖結構性質。

3 不包含｛4，8，9｝－圈平面圖結構的性質

要證明這7個性質，需要介紹一個定義，即不包含｛4，8，9｝－圈平面圖G 的極小性：設f0為圖G中的一個i面，i∈｛3，5，6，7，10，11｝，G［V（f0）］有一個3－染色φ，但φ不可延拓到整個圖G上。

不包含｛4，8，9｝－圈平面圖G 具有如下性質：

1）C0不含弦。即：若v∈V（C0），d（v）≥3，則v有且僅有兩個鄰點在C0上；

2）G是2－連通的，G中的任意面的邊界都是一個圈；

3）對任意v∈int（C0），d（v）≥3；

4）G不含長度為≤11的分離圈；

5）G中的內部非分離6－圈不含弦，且不與3－圈相鄰；

6）G中沒有包含非三角弦的10－圈和11－圈；

7）G中的內部非分離6－圈不與5－圈相鄰。

證明：

1）假若uv為C0上的一條弦。從G中刪去uv，得新圖記為G′，則 w（G′）≤w（G），σ（G′）＜σ（G）。顯然G′仍是一個連通的平面圖。則由G的極小性知，φ可延拓到G′上。由于φ是G［V（f0）］的一個3－染色，故φ（u）≠φ（v）。從而得到φ可延拓到G上，即圖G是3－可染的，與圖G的極小性矛盾。故C0不含弦。若v∈V（C0），d（v）≥3，則由C0不含弦，根據定義v有且僅有兩個鄰點在C0上。

2）假若圖G有一個割點v連接兩個塊B1和B2＝G－（V（B1）＼｛v｝）。顯然，塊Bi，i＝1，2，仍是不包含｛4，8，9｝－圈的連通平面圖，且w（Bi）≤w（G），σ（Bi）＜σ（G）。若C0是B1，B2的外部面邊界的并集，則由G的極小性知，C0的3－染色可分別延拓到B1和B2上，從而得到G的一個3－染色，與圖G的極小性矛盾。否則，若C0不是B1，B2的外部面邊界的并集，則C0?B2。由G的極小性知，C0的3－染色可延拓到B2上。若B1是3－可染的，適當交換B1中點的染色，使v在B1中的染色與其在B2中的一致，則可得到G的一個3－染色，與圖G的極性矛盾。下面我們只需證B1確實是3－可染的。

若B1不含6－圈，則由文獻［5］中所證明的每個不包含｛4，6，8，9｝－圈的平面圖是3－可選擇的，得B1是3－可染的；若B1至少包含一個6－圈C，由于圖G不含4－圈，8－圈，故C至多只有一條弦。故C有一個3－染色，由G的選取知，C的3－染色可分別延拓到B1中C的外部和內部上，即B1是3－可染的。

3）假若v∈int（C0），d（v）≤2。記從圖G 中刪去頂點v得到的新圖為G′，則w（G′）≤w（G），且σ（G′）＜σ（G），G′仍為連通的平面圖。由G 的選擇，φ可延拓到G′上，由于d（v）≤2，故易對v染色，從而得到G的一個3－染色，與圖G的極小性矛盾。

4）假若G中存在這樣的分離圈Ci，｜Ci｜≤11。顯然，i?｛4，8，9｝，則由G 的極小性，φ可延拓到ext（Ci）上，i∈（3，5，6，7，10，11｝。由G 的極小性知，去掉Ci中的可能弦，可將φ在Ci上的限制延拓到int（Ci）上，從而G是3－可染的，與圖G的選擇矛盾。

5）假若G中有一個內部的非分離6－圈C＝u0u1u2u3u4u5u0，且C含弦xy。由于G不含4－圈，故可設xy＝u1u5時：若v0是內部點，則圈u1u0u5u1在圖中是一個分離的3－圈，與性質4）結論矛盾；若u0不是內部點，則u1u2u3u4u5u1在圖中是一個分離的5－圈，與性質4）結論矛盾，故G中的內部非分離6－圈不含弦。如圖1所示。

圖1 內部含非分離6－圈的平面圖

由于圖G中的內部非分離6－圈不含弦，所以G中與內部非分離3－圈只可能是一般相鄰，設圖G中存在與內部非分離的6－圈一般相鄰的3－圈，如圖2所示。

圖2 非分離6－圈與3－圈相鄰的平面圖

此時所得的新圖記為G′，刪去弦xy，適當調整染色，可使x，y染不同的顏色，則可得G是3－可染。由G的選取可知，φ可延拓到G′上，從而得到φ可延拓到G上。與圖G的極小性矛盾，故G中的內部非分離6－圈不與3－圈相鄰。

6）假若圖G中有一個含非三角弦e的圈C11。由于圖G 中不含4－，8－，9－圈，故弦e只能把C分成一個C5和一個C6。如果int（C5）和int（C6）都是空集的話，那么去掉這條非三角弦，C0的染色φ可延拓到去掉弦后的新圖G′上，φ從而可延拓到圖G 上，與圖G的極性矛盾。如果int（C5）和int（C6）至少一個非空的話，則可得到分離的5－圈或分離的6－圈，與性質4）結論矛盾。圖G中有一個含非三角弦e的圈10－圈的情形類似證明。

7）先證：若G中的內部非分離6－圈與5－圈是相鄰的，也只可能是一般相鄰的。設C5＝xyv1v2v3x和非分離6－圈C6＝xyu1u2u3u4x是相鄰的，如圖3所示。

圖3 非分離6－圈與5－圈相鄰的平面圖

首先v1?V（C6）：若v1＝u1，y是內部點，則xv3v2v1yx在圖中是一個分離的5－圈，與性質4）結論矛盾；若y不是內部點，則xv3v2u1u2u3u4x在圖中是一個分離的7－圈，與性質4）結論矛盾；若v1∈｛u2，u3，u4｝，則與內部非分離6－圈不含弦矛盾；由對稱性可知，v3?V（C6）；其次v2?V（C6）：若v2＝u1，則會產生一個4－圈u1yxv3u1，與不包含｛4，8，9｝－圈的平面圖條件矛盾；若v2＝u2，則會產生一個4－圈u2u1yv1u2，與不包含｛4，8，9｝－圈的平面圖條件矛盾；若v2＝u3，則會產生一個4－圈u2u4xv3u3，與不包含｛4，8，9｝－圈的平面圖條件矛盾；由對稱性得，v2≠u4。

但是內部非分離6－圈與5－圈不可能是一般相鄰的，否則會產生一個含非三角弦的11－圈。

4 結 語

根據文獻［5］給出了定理：每個不包含｛4，6，8，9｝－圈的平面圖是3－可選擇的。嘗試將6－圈的條件去掉，研究不包含｛4，8，9｝－圈的平面圖結構的一些性質，這些性質為研究“每個不包含｛4，8，9｝－圈的平面圖是3－可染的”的命題提供了前提依據。

［1］J Yin，K Wu.Theory and its algorithm［M］.Hefei：China University of Science and Technology，2003.

［2］P Erdos，A L Rubin，H Taylor.Choosability in graphs［J］.Congr Numer，1979，26：125－157.

［3］R Steinberg.The state of the three color problem［J］.Diserete Math.，1993，55：211－248.

［4］D P Sanders，Y Zhao.A note on the three coloring problem［J］.Graphs Combin，1995，11：92－94.

［5］L Shen，Y Q Wang.A sufficient condition for aplanar graph to be 3－choosable［J］.Inform Process Lett，2007，104：146－154.

［6］W Wang，M Chen.Planar graphs without 4，6and 8－cycles are 3－colorable［J］.Sci.China Ser AMath.，2007，50（11）：1552－1562.

［7］H Lu，Y Wang，W Wang，et al.On the 3－colorability of planar graphs without 4－，7－and 9－cycles［J］.Discrete Mathematics，2009，309：4596－4607.

［8］D Liao.On the 3－colorability of planar graphs without 4－，6－and 9－cycles［D］：［Master’s Degree Thesis］.Fuzhou：Fuzhou University，2010.