方冬云

（莆田學(xué)院 數(shù)學(xué)系，福建 莆田 351100）

1 基本術(shù)語(yǔ)及符號(hào)［1］

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

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

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

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

2 一些平面圖研究成果的簡(jiǎn)介

平面有限簡(jiǎn)單無向圖（簡(jiǎn)稱平面圖）的點(diǎn)染色問題起源于著名的四色猜想，接著，人們?cè)囍鴮?duì)4－可選擇的平面圖作了一些特征刻畫，且關(guān)于2－可選擇這樣的問題，Erdos［2］等人已經(jīng)做了特征化的論述，因此，許多學(xué)者對(duì)平面圖3－可染（可選擇）問題做了一系列的討論與研究：

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

3 不包含｛4，8，9｝－圈平面圖結(jié)構(gòu)的性質(zhì)

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

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

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

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

3）對(duì)任意v∈int（C0），d（v）≥3；

4）G不含長(zhǎng)度為≤11的分離圈；

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

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

7）G中的內(nèi)部非分離6－圈不與5－圈相鄰。

證明：

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

2）假若圖G有一個(gè)割點(diǎn)v連接兩個(gè)塊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的一個(gè)3－染色，與圖G的極小性矛盾。否則，若C0不是B1，B2的外部面邊界的并集，則C0?B2。由G的極小性知，C0的3－染色可延拓到B2上。若B1是3－可染的，適當(dāng)交換B1中點(diǎn)的染色，使v在B1中的染色與其在B2中的一致，則可得到G的一個(gè)3－染色，與圖G的極性矛盾。下面我們只需證B1確實(shí)是3－可染的。

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

3）假若v∈int（C0），d（v）≤2。記從圖G 中刪去頂點(diǎn)v得到的新圖為G′，則w（G′）≤w（G），且σ（G′）＜σ（G），G′仍為連通的平面圖。由G 的選擇，φ可延拓到G′上，由于d（v）≤2，故易對(duì)v染色，從而得到G的一個(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中有一個(gè)內(nèi)部的非分離6－圈C＝u0u1u2u3u4u5u0，且C含弦xy。由于G不含4－圈，故可設(shè)xy＝u1u5時(shí)：若v0是內(nèi)部點(diǎn)，則圈u1u0u5u1在圖中是一個(gè)分離的3－圈，與性質(zhì)4）結(jié)論矛盾；若u0不是內(nèi)部點(diǎn)，則u1u2u3u4u5u1在圖中是一個(gè)分離的5－圈，與性質(zhì)4）結(jié)論矛盾，故G中的內(nèi)部非分離6－圈不含弦。如圖1所示。

圖1 內(nèi)部含非分離6－圈的平面圖

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

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

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

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

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

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

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

但是內(nèi)部非分離6－圈與5－圈不可能是一般相鄰的，否則會(huì)產(chǎn)生一個(gè)含非三角弦的11－圈。

4 結(jié) 語(yǔ)

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

［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.