劉維嬋

LIU Weichan

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西安 710071

School of Mathematics and Statistics,Xidian University,Xi’an 710071,China

1　引言

圖論是一門古老的數(shù)學(xué)分支，它起源于1736年歐拉對于哥尼斯堡七橋問題的研究。近年來，圖論學(xué)科的發(fā)展非常迅速且應(yīng)用廣泛，已滲透到諸如語言學(xué)、物理學(xué)、化學(xué)、電訊工程、計算機科學(xué)以及數(shù)學(xué)的其他分支中，特別在計算機科學(xué)中，圖論在如形式語言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)等方面均扮演著重要的角色。

本文研究圖的拓?fù)浣Y(jié)構(gòu)，只考慮簡單圖。如果一個圖可以畫（嵌入）在平面上，使得不同的邊互不交叉，則稱這樣的圖是平面圖，否則稱為非平面圖。一個平面圖在平面上的嵌入稱為平圖。對于平圖G，用V(G)、E(G)、F(G)分別表示它的點集合、邊集合、面集合。著名的歐拉公式表明：

設(shè)G為一個圖在平面上的嵌入，如果圖G上存在交叉，則必然是G的某兩條邊交叉產(chǎn)生的，于是G中的每個交叉c都可以與G中的4個頂點（即兩條交叉邊上的4個頂點）所構(gòu)成的點集建立對應(yīng)關(guān)系，稱這個對應(yīng)關(guān)系為θ。如果對于G中任何兩個不同的交叉（如果存在的話）c1與c2，有|θ(c1)?θ(c2)|≤1，則稱圖 G 是NIC-平面圖。NIC-平面圖的概念是由Zhang[1]于2014年提出的。容易看出，每個平面圖都是NIC-平面圖。

設(shè)?是一個圖類，如果對于?中的任何一個圖G，都存在一條邊uv以及一個與圖G的選擇無關(guān)的常數(shù)ω，使得d(u)+d(v)≤ω，則稱圖類?含有輕邊。Kotzig[2]證明了每個3-連通的平面圖都含有一條邊uv，其兩個頂點的度和至多為13。Fabrici與Madaras[3]證明了每個3-連通的1-平面圖都含有一條邊uv，其兩個頂點的度都不會超過20。具有最小度限制條件的1-平面圖的輕邊或其他輕子圖的存在性的研究可參見文獻(xiàn)[4-12]。

下文中，對于NIC-平面圖G，用δ(G)表示它的最小度，即度數(shù)（點所關(guān)聯(lián)的邊的條數(shù)）最小的頂點的度數(shù)；用g(G)表示它的圍長，即圖G所包含的所有圈中長度（圈所關(guān)聯(lián)的邊的條數(shù)）最短的圈的長度；用GX表示圖G的關(guān)聯(lián)平面圖，即將圖G的所有交叉全部看成是一個新的度數(shù)為4的點所得到的平圖，這些新的點稱為圖GX的假點，其余的點稱為圖GX的真點；在圖GX中關(guān)聯(lián)假點的面稱為假面，其余的面稱為真面；k-點（面）或k+-點（面）指的是度數(shù)為k或至少為k的點（面）。其余未明確指出的定義或者記號可參閱文獻(xiàn)[7]。

設(shè)G是一個圍長至少為5的NIC-平面圖。現(xiàn)從圖G的每一對交叉邊中去除一條，得到圖H。容易看出，圖H是一個圍長至少為5的平面圖。根據(jù)歐拉公式（1），可以得到[13]：

另一方面，Zhang[1]于2014年證明了圖G的交叉數(shù)至多為3(|V(G)|-2)/5，因此：

從而圖G的平均度為2|E(G)|/|V(G)|＜5，由此可得δ(G)≤4，即每個圍長至少為5的NIC-平面圖都含有一個度數(shù)不超過4的點。基于此，本文將研究圍長至少為5且最小度為4的NIC-平面圖的輕邊存在性，并探討其在定向染色中的應(yīng)用。

2　NIC-平面圖的輕邊存在性

定理1設(shè)G是NIC-平面圖，如果δ(G)=4且g(G)≥5，則G存在邊uv，其中d(u)=d(v)=4。

證明 假設(shè)該命題的結(jié)論不成立，即對于G的任何一條邊uv，當(dāng)d(u)=4時，有d(v)≥5。

考慮圖G的關(guān)聯(lián)平面圖GX，由于它是平面圖，故根據(jù)歐拉公式（1），有：

對于圖GX的每個點v，定義權(quán)值c(v)=d(v)-6，對于每個面 f，定義權(quán)值c(f)=2d(f)-6。從而由式（2）可知：

接下來，定義權(quán)轉(zhuǎn)移規(guī)則如下：

（R1）每個4-面向其關(guān)聯(lián)的假4-點轉(zhuǎn)移1/2。

（R2）設(shè) f=uvwx為4-面且 x為假4點，如果v是真4-點，則 f向v轉(zhuǎn)移5/6；如果u或w是真4-點，則 f向u或w轉(zhuǎn)移1/2。

（R3）每個4+-面向其關(guān)聯(lián)的5-點轉(zhuǎn)移1/3。

（R4）設(shè) f是一個5+-面，v是其關(guān)聯(lián)的真4-點，如果v在 f的兩個相鄰點都是假4-點，則 f向v轉(zhuǎn)移7/6；否則，f向v轉(zhuǎn)移1。

（R5）每個5+-面向其關(guān)聯(lián)的假4-點轉(zhuǎn)移3/4。

設(shè)c*(v)與c*(f)為圖GX中的點v與面 f在執(zhí)行完上述權(quán)轉(zhuǎn)移規(guī)則后的最終權(quán)值。

情況1點v是假4-點

如果點v關(guān)聯(lián)4個4+-面，則由（R1）與（R5）可知：

如果點v關(guān)聯(lián)3-面，則由于圖G是NIC的，并且其圍長至少為5，推得點v關(guān)聯(lián)2個5+-面與1個4+-面，從而根據(jù)（R1）與（R5）可知：

情況2點v是真4-點

記v1,v2,v3,v4為點v在GX中的4個鄰點，并且f1,f2,f3,f4分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv1}關(guān)聯(lián)的面。

如果v在GX中的鄰點都是真點，那么由圖G的圍長至少為5可得點v關(guān)聯(lián)4個4+-面，從而根據(jù)（R2）與（R4）得到：

如果v在GX中的鄰點有假點，則：

（1）當(dāng)v在GX中的鄰點中有且僅有1個假點時，若點 v關(guān)聯(lián)4個4+-面時，由（R2）與（R4）得式（4）。若點v關(guān)聯(lián)1個3-面時，則其關(guān)聯(lián)3個4+-面，且其中1個是5+-面（否則與圍長限制條件矛盾），因此根據(jù)（R2）與（R4），可得：

（2）當(dāng)v在GX中的鄰點中有且僅有2個假點時，根據(jù)對稱性，考慮兩種子情況。

其一，如果v1,v2是假點，則 f1必定為5+-面（否則與NIC-平面圖的定義矛盾），此時若 f3是5+-面，則根據(jù)（R4）有：

若 f3是4-面，則其必定為假4-面，由（R2）與（R4）得：

其二，如果v1,v3是假點，則當(dāng) f1,f2,f3,f4均為4+-面時，由（R2）與（R4）可得式（4）。當(dāng)它們中有至少2個3-面時，則其中至少有2個5+-面，故由（R4）得：

當(dāng) f1,f2,f3,f4中有且只有1個3-面時，則其中有2個4+-面與1個5+-面，從而根據(jù)（R2）與（R4）有：

（3）當(dāng)v在GX中的鄰點中有且僅有3個假點時，不妨設(shè)其為v1,v2,v3，此時若 f1,f2,f3,f4均為4+-面時，由（R2）與（R4）得式（4）。若 f1,f2,f3,f4中存在3-面時，則其必為 f3或者 f4，不妨設(shè)其為 f4?，F(xiàn) f3為4+-面且f1,f2為5+-面，故由（R2）與（R4）得：

（4）當(dāng)v在GX中的鄰點中有4個假點時，則其關(guān)聯(lián)4個 4+-面，從而由（R2）與（R4）得式（4）。

情況3點v是5-點

記v1,v2,v3,v4,v5為點v在GX中的5個鄰點，并且 f1,f2,f3,f4,f5分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv5},{vv5,vv1}關(guān)聯(lián)的面。如果 5個面中至少有3個4+-面，則根據(jù)（R3）可得：

否則這5個面中至少有3個3-面，并且其中2個必定相鄰。因此不妨設(shè) f1,f2為3-面，由于圖G的圍長至少為5，故 f1,f2都為假3-面。此時有兩種情況：其一，當(dāng)v2是假點時，則v1,v3為真點，從而vv1v3構(gòu)成了G中的一個三角形，矛盾；其二，當(dāng)v2是真點時，則v1,v3為假點，此時|θ(v1)?θ(v3)| ≥2，與NIC-平面圖的定義矛盾。

情況4面 f是4-面

由于圖G的圍長至少為5，故 f是假4-面。再由于圖是NIC-平面的，其恰好關(guān)聯(lián)1個假4-點。此時如果 f關(guān)聯(lián)（至少）2個真4-點，其必定關(guān)聯(lián)1個5+-點，并且這2個真4-點與 f所關(guān)聯(lián)的假4-點相鄰，于是根據(jù)（R1），（R2）與（R3），有：

若 f關(guān)聯(lián)恰好1個真4-點，則由前3條規(guī)則可得：

若 f不關(guān)聯(lián)真4-點，則由（R1）與（R3）可得：

情況5面 f是5+-面

當(dāng) d(f)=5時，則根據(jù)（R3）、（R4）與（R5）可知當(dāng) f關(guān)聯(lián)2個真4-點，2個假4-點與1個5-點時，f向外轉(zhuǎn)移的權(quán)值最多，從而：

當(dāng)d(f)=d≥6時，設(shè) f關(guān)聯(lián)a個真4-點與b個假4-點。因為真4-點與真4-點不相鄰并且假4-點與假4-點不相鄰，因此根據(jù)（R3）、（R4）與（R5）可知：

最后，由于6+-點與3-面不參與權(quán)轉(zhuǎn)移，故它們的最終權(quán)值和初始權(quán)值相同，為非負(fù)。

至此，已經(jīng)證明了圖GX中的所有點與面的最終權(quán)值均為非負(fù)，即得到：

由于權(quán)只在圖GX中的所有點與面的內(nèi)部進(jìn)行轉(zhuǎn)移，故轉(zhuǎn)移前后的總權(quán)值和不變，即根據(jù)式（3）有：

此與式（5）矛盾。

3　結(jié)論的推廣及其在定向染色中的應(yīng)用

本章首先給出定理1的一個重要推論。

推論1設(shè)G是一個圍長至少為5的NIC-平面圖，則G存在一個度數(shù)至多為3的點，或者兩個相鄰的度數(shù)為4的點。

證明 如果圖G不存在度數(shù)至多為3的點，則δ(G)≥4。另一方面，由第1章最后一段的分析可知δ(G)≤4，于是δ(G)=4。此時根據(jù)定理1可知圖G含有兩個相鄰的度數(shù)為4的點。

設(shè)G是一個簡單無向圖，現(xiàn)將圖G的每一條邊uv進(jìn)行定向（令u指向v或者v指向u）得到一個有向圖。圖的一個定向k-染色指的是一個從V到{1,2,…,k}的映射c，其對于圖的每一條弧滿足：（1）c(u)≠c(v)；（2）不存在弧使得c(x)=c(u)且c(y)=c(v)。從而使得圖具有一個定向k-染色的最小整數(shù)k稱為圖的定向染色數(shù)，記為χo。設(shè)Θ(G)為對無向圖G進(jìn)行定向后得到的所有可能的有向圖的集合，則無向圖G定向染色數(shù)定義為

2007年，Esperet與Ochem[14]證明了如果圖G是不滿足χo(G)≤67的極小反例，則圖G不含有度數(shù)至多為3的點，亦不含有兩個相鄰的度數(shù)為4的點。因此，根據(jù)推論1可得到如下一個結(jié)果。

定理2設(shè)G是一個圍長至少為5的NIC-平面圖，則 χo(G)≤67。

注意到Raspaud與Sopena[15]證明了每個平面圖G滿足χo(G)≤80，這也是到目前為止最好的結(jié)果。由于NIC-平面圖類包含平面圖類，故從一定的意義上來看定理2是上述結(jié)論的推廣與改進(jìn)。

4　結(jié)論

綜上所述，本文證明了每個圍長至少為5且最小度為4的NIC-平面圖含有一條邊，其2個頂點的度數(shù)都是4，從而推出每個圍長至少為5的NIC-平面圖的定向染色數(shù)至多為67。

定理1中，關(guān)于NIC-平面圖的圍長的下界5是否可以降低是一個值得繼續(xù)考慮的問題。此外，利用其他方式得到NIC-平面圖的定向染色數(shù)的較好上界也是一個有意義的研究方向。

參考文獻(xiàn)：

[1]Zhang X.Drawing complete multipartite graphs on the plane with restrictions on crossings[J].Acta Mathematica Sinica：English Series，2014，30（12）：2045-2053.

[2]Kotzig A.Contribution to the theory of Eulerian polyhedra[J].Mat ?as SAV：Math Slovaca，1955，5：111-113.

[3]Fabrici I，Madaras T.The structure of 1-planar graphs[J].Discrete Mathematics，2007，307：854-865.

[4]Hudák D，?ugerek P.Light edges in 1-planar graphs with prescribed minimum degree[J].Discussiones Mathematicae Graph Theory，2012，32（3）：545-556.

[5]田京京，聶玉峰.度限制條件下的IC平面圖類中輕弦4-圈的存在性[J].計算機工程與應(yīng)用，2016，52（20）：26-28

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

[7]Tian J，Zhang X，Light triangles in plane graphs with nearindependent crossings[J].Utilitas Mathematica，2015，97：399-405.

[8]Zhang X.A note one the weight of triangle in 1-planar graphs with minimum degree 6[J].Utilitas Mathematica，2014，93：129-134.

[9]Zhang X，Liu G.On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree[J].Ars Mathematica Contemporanea，2014，7（2）：233-243.

[10]Zhang X，Liu G，Wu J.Light subgraphs in the family of 1-planar graphs with high minimum degree[J].Acta Mathematica Sinica：English Series，2012，28（6）：1155-1168.

[11]Zhang X，Wu J，Liu G.New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree[J].Discrete Mathematics and Theoretical Computer Science，2011，13（3）：9-16.

[12]張欣，劉桂真，吳建良.1-平面圖的結(jié)構(gòu)性質(zhì)及其在無圈邊染色上的應(yīng)用[J].中國科學(xué)：數(shù)學(xué)，2010，40（10）：1025-1032.

[13]Bondy J A，Murty U S R.Graph theory with applications[M].New York：North-Holland，1976.

[14]Esperet L，Ochem P.Oriented colorings of 2-outerplanar graphs[J].Information Processing Letters，2007，101：215-219.

[15]Raspaud A，Sopena E.Good and semi-strong colorings of oriented planar graphs[J].Information Processing Letters，1994，51（4）：171-174.