具有度限制條件的IC平面圖類中輕3－圈的存在性

田京京，聶玉峰

（1西北工業(yè)大學(xué)理學(xué)院，陜西西安710129；

2陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中723000）

具有度限制條件的IC平面圖類中輕3－圈的存在性

田京京1，2，聶玉峰1

（1西北工業(yè)大學(xué)理學(xué)院，陜西西安710129；

2陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中723000）

利用權(quán)轉(zhuǎn)移方法證明了每個(gè)最小度至少為5并且最小邊度至少為11的IC－平面圖G含有一個(gè)最大度max｛d（u），d（v），d（w）｝≤17的3－圈。

IC－平面圖；權(quán)轉(zhuǎn)移方法；3－圈

本文僅考慮簡(jiǎn)單的有限無向圖。設(shè)G是一個(gè)平面圖，分別用V（G）、E（G）、F（G）、Δ（G）、δ（G）來表示它的點(diǎn)集合、邊集合、面集合、最大度和最小度。特別地，G中任意一條邊uv所關(guān)聯(lián)的點(diǎn)u、v度的和d（u）+d（v）稱為邊uv的度。用k－、k+－和k－－點(diǎn)或面分別表示一個(gè)點(diǎn)或面的度為k、至少為k和至多為k。其余定義若無特殊說明，均參考文獻(xiàn)［1］。

一個(gè)圖稱為是1－平面的當(dāng)且僅當(dāng)它可以畫在一個(gè)平面上使其任何一條邊最多交叉另外一條邊。1－平面圖是Ringel［2］于1965年研究平面圖的點(diǎn)－面染色時(shí)提出來的，至今還有許多未被研究的問題。

設(shè)G為一個(gè)圖在平面上的一個(gè)嵌入，如果圖G上存在交叉點(diǎn)，則必然是G的某兩條邊交叉產(chǎn)生的，于是G中的每個(gè)交叉點(diǎn)c都可以與G中的4個(gè)頂點(diǎn)（即兩條交叉邊上的4個(gè)頂點(diǎn)）所構(gòu)成的點(diǎn)集建立對(duì)應(yīng)關(guān)系，稱這個(gè)對(duì)應(yīng)關(guān)系為S。顯然，在一個(gè)好的1－平面圖畫法（即交叉點(diǎn)最少的畫法）中，對(duì)于任意兩個(gè)交叉點(diǎn)c1、c2存在｜S（c1）∩S（c2）｜≤2。據(jù)此，定義1－平面圖的兩個(gè)子類，若滿足｜S（c1）∩S（c2）｜＝0，則稱該1－平面圖為IC－平面圖，若｜S（c1）∩S（c2）｜≤1，則稱該1－平面圖為NIC－平面圖。IC－平面圖的概念是由文獻(xiàn)［3］于2010年提出的，他們證明了每個(gè)IC－平面圖都是5－可染的，并且色數(shù)的上界5是緊的。NIC－平面圖的概念則是由文獻(xiàn)［4］于2014年提出的，其中給出了完全多部圖的NIC－平面性與IC－平面性的完全刻畫。

設(shè)H是一個(gè)連通圖，G是一個(gè)圖類，K是一個(gè)給定的圖。如果任意的圖G∈G都包含一個(gè)與圖K同構(gòu)的子圖H，其在圖G中的最大度是一個(gè)不超過某個(gè)與圖G的選擇無關(guān)的常數(shù)，則稱圖K在圖類G中是輕的。尋找給定圖類中輕的子圖是圖結(jié)構(gòu)理論中的一類經(jīng)典問題。例如，文獻(xiàn)［5］得出一個(gè)著名的結(jié)論：任何一個(gè)最小度至少為5的平面圖包含一個(gè)3－圈xyz，其滿足max｛d（u），d（v），d（w）｝≤17，并且該結(jié)論中的上界17是最優(yōu)的。文獻(xiàn)［5］的定理說明：3－圈在最小度至少為5的平面圖類中是輕的。2014年，文獻(xiàn)［6］證明了3－圈在最小度至少為5并且最小邊度至少為12的1－平面圖類中是輕的，并提出如下猜想：

猜想 3－圈在最小度至少為5并且最小邊度至少為11的1－平面圖類中是輕的。

本文將證明猜想對(duì)于1－平面圖的子類IC－平面圖是成立的。

1 主要定理及其證明

設(shè)G是IC－平面圖。如果將G中的所有交叉點(diǎn)全部看成是4度點(diǎn)，則可以得到一個(gè)交叉數(shù)為0的圖，即平面圖G×，下面稱圖G×為G的關(guān)聯(lián)圖。設(shè)v是圖G×中的的一個(gè)點(diǎn)，如果v∈V（G×）＼V（G），則稱v是G×的一個(gè)假點(diǎn)或稱v是G的一個(gè)交叉點(diǎn)。如果圖G×的一個(gè)面f關(guān)聯(lián)至少一個(gè)假點(diǎn)，則稱f為G×的一個(gè)假面，否則稱f為G×的一個(gè)真面。設(shè)v是G×中的k－點(diǎn)，v1、v2、…、vk是v在G×中按順時(shí)針排列的所有鄰點(diǎn)。在G×中與邊vvi和vvi+1關(guān)聯(lián)的面記為fi，其中1≤i≤k，并記vk+1∶＝v1。

定理 每個(gè)最小度至少為5并且最小邊度至少為11的IC－平面圖含有一個(gè)3－圈xyz，其滿足max｛d（u），d（v），d（w）｝≤17。

證明 設(shè)G是定理1的反例，G×是G的關(guān)聯(lián)圖。給G×中的每個(gè)點(diǎn)v賦初始權(quán)值c（v）＝d（v）－6，同時(shí)給G×中的每個(gè)面f賦初始權(quán)值c（f）＝2d（f）－6，運(yùn)用平面圖G×上的歐拉公式，有

現(xiàn)在，按照如下規(guī)則對(duì)V（G×）∪F（G×）上的所有元素重新分配權(quán)值。

（1）G×中每個(gè)18+－點(diǎn)向它所關(guān)聯(lián)的面轉(zhuǎn)移；

（2）設(shè)f＝xyz是G×中的一個(gè)3－面，且x是一個(gè)18+－點(diǎn)。

（2.1）若y和z是5－－點(diǎn)，則f向y、z分別轉(zhuǎn)移。

（2.2）若y是一個(gè)18+－點(diǎn)且z是4－點(diǎn)或5－點(diǎn)，則f向z轉(zhuǎn)移。

（2.3）若y是一個(gè)4－點(diǎn)或5－點(diǎn)且z是一個(gè)度介于6與17之間的點(diǎn)，則f向y轉(zhuǎn)移。

（3）每個(gè)4+－面向它關(guān)聯(lián)的4－點(diǎn)轉(zhuǎn)移1，每個(gè)4+－面向它關(guān)聯(lián)的5－點(diǎn)轉(zhuǎn)移。

設(shè)c′（x）為元素x∈V（G×）∪F（G×）在應(yīng)用以上權(quán)轉(zhuǎn)移規(guī)則后得到的新權(quán)值，下面證明對(duì)于每個(gè)x∈V（G×）∪F（G×）都有c′（x）≥0。因此，矛盾。

設(shè)f∈F（G×），若d（f）＝3，則由（1）和（2）知c′（f）＞0。若4≤d（f）≤5，則根據(jù)IC－平面圖的定義知f至多關(guān)聯(lián)1個(gè)4－點(diǎn)。另一方面，由于G的最小邊度至少為11，故f至多關(guān)聯(lián)2個(gè)5－點(diǎn)，從而由（3）可得

若d（f）≥6，則由（3）可得

c′（f）≥2d（f）－6－d（f）＝d（f）－6≥0。

設(shè)v∈V（G×）。若d（v）≥18，則由（1）得

根據(jù)規(guī)則（1）—（3），圖G×中介于6到17度的點(diǎn)不參與權(quán)轉(zhuǎn)移，因此若6≤d（v）≤17，則必有

c′（v）＝c（v）＝d（v）－6≥0。

設(shè)d（v）＝4。若v至少關(guān)聯(lián)2個(gè)4+－面，則由（3）可得

c′（v）≥4－6+2×1＝0。

若v僅關(guān)聯(lián)1個(gè)4+－面，不妨設(shè)其為f1，則f2、f3與f4均為3－面。若v3是5－點(diǎn)，則v2與v4中必有一個(gè)18+－點(diǎn)，否則圖G中的3－圈v2v3v4即為所求。不妨設(shè)v2是18+－點(diǎn)，從而根據(jù)（2.2），f2向v轉(zhuǎn)移，于是再結(jié)合（3）可得因此，可假設(shè)v3是6+－點(diǎn)。同時(shí)，由對(duì)稱性可知，v4也是6+－點(diǎn)。由于圖G不含該待證定理中所述的輕3－圈，故v1與v2必為18+－點(diǎn)，從而根據(jù)（2.2）與（2.3），f2與f4分別向v轉(zhuǎn)移至少。最后再結(jié)合（3），可得

若v僅關(guān)聯(lián)3－面，即f1、f2、f3與f4均為3－面。由于G是一個(gè)反例，v1、v2、v3與v4中必至少有2個(gè)18+－點(diǎn)。根據(jù)對(duì)稱性，考慮兩種情況。首先假設(shè)v1與v2是18+－點(diǎn)。由于G的最小邊度至少為11，v3與v4中至少有一個(gè)6+－點(diǎn)，不妨假設(shè)d（v3）≥6。則由（2.2）與（2.3），f1向v轉(zhuǎn)移，f2向v轉(zhuǎn)移至少，于是有

其次，假設(shè)v1與v2是18+－點(diǎn)。由于v2v4∈E（G），v2與v4中必有一個(gè)6+－點(diǎn)，不妨設(shè)d（v2）≥6。則由（2.2）與（2.3），f1與f2分別向v轉(zhuǎn)移至少，由（2.1）—（2.3），f3與f4分別向v轉(zhuǎn)移至少。因此有

設(shè)d（v）＝5。若v至少關(guān)聯(lián)2個(gè)4+－面，則由（3）可得

若v只關(guān)聯(lián)1個(gè)4+－面，不妨設(shè)其為f1，則f2、f3、f4與f5均為3－面。由圖G的IC－平面性，f2、f3、f4與f5中必有一個(gè)是真3－面，不妨假設(shè)是f2，由于反例圖G的最小邊度至少為11，故v2與v3均為6+－點(diǎn)，并且二者之間必有一個(gè)18+－點(diǎn)，于是由（2.2）與（2.3）知f2向v轉(zhuǎn)移至少。此時(shí)考慮f1，由（3）得

若v關(guān)聯(lián)的全是3－面，則在G×中v與最多一個(gè)4－點(diǎn)相鄰，否則與圖G的IC－平面性矛盾。這說明f1、f2、f3、f4與f5中至少有3個(gè)是真3－面。由于G是反例，G×中的每個(gè)真3－面都關(guān)聯(lián)至少一個(gè)18+－點(diǎn)，于是由（2.1）—（2.3）知每個(gè)與點(diǎn)v關(guān)聯(lián)的真3－面向v轉(zhuǎn)移至少。因此，

2 結(jié)論

本文利用權(quán)轉(zhuǎn)移的方法證明文獻(xiàn)［6］提出的猜想對(duì)于1－平面圖的子類IC平面圖成立，且IC平面圖G含有一個(gè)最大度max｛d（u），d（v），d（w）｝≤17的3－圈。

［1］Bondy J A，Murty U S R.Graph theory with applications［M］.New York：North－Holland，1976.

［2］Ringel G.Ein sechsfarbenproblem auf der Kugel［J］.Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg，1965，29：107－117.

［3］Kral D，Stacho L.Coloring plane graphs with independent crossings［J］.Journal of Graph Theory，2010，64（3）：184－205.

［4］Zhang X.Drawing complete multipartite graphs on the plane with restrictions on crossings［J］.Acta Mathematica Sinica，2014，30（12）：2045－2053.

［5］Borodin O V.Solution of problems of Kotzig and Gruunbaum concerningthe isolation of cycles in planar graphs［J］.Mathematical Notes，1989，46：835－837.

［6］Zhang X.Light 3－cycles in 1－planar graphs with degree restrictions［J］.Bulletin of the Korean Mathematical Society，2014，51（2）：511－517.

〔責(zé)任編輯 宋軼文〕

Light 3－cycles in IC－planar graphs with degree restrictions

TIAN Jingjing1，2，NIE Yufeng1
（1School of Natural and Applied Sciences，Northwestern Polytechnical University，Xi′an 710129，Shaanxi，China；2School of Mathematics and Computer Science，Shaanxi University of Technology，Hanzhong 723000，Shaanxi，China）

It is proved by discharging method that every IC－planar graph Gwith minimum vertex degree at least 5and minimum edge degree at least 11contains a 3－cycle xyz with max｛d（u），d（v），d（w）｝≤17.

IC－planar graph；discharging method；3－cycle

05C10

O157.5

A

1672－4291（2015）05－0001－03

10.15983／j.cnki.jsnu.2015.05.151

2015－03－19

國(guó)家自然科學(xué)基金（11301410，11461038）

田京京，女，副教授，博士研究生，主要研究方向?yàn)閳D論及組合優(yōu)化。E－mail：tianjingjing2004＠163.com