NIC-平面圖中的輕邊存在性及其定向染色

劉維嬋

LIU Weichan

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

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

1　引言

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

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

設(shè)G為一個(gè)圖在平面上的嵌入，如果圖G上存在交叉，則必然是G的某兩條邊交叉產(chǎn)生的，于是G中的每個(gè)交叉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)系為θ。如果對(duì)于G中任何兩個(gè)不同的交叉（如果存在的話）c1與c2，有|θ(c1)?θ(c2)|≤1，則稱圖 G 是NIC-平面圖。NIC-平面圖的概念是由Zhang[1]于2014年提出的。容易看出，每個(gè)平面圖都是NIC-平面圖。

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

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

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

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

從而圖G的平均度為2|E(G)|/|V(G)|＜5，由此可得δ(G)≤4，即每個(gè)圍長(zhǎng)至少為5的NIC-平面圖都含有一個(gè)度數(shù)不超過(guò)4的點(diǎn)。基于此，本文將研究圍長(zhǎng)至少為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é)論不成立，即對(duì)于G的任何一條邊uv，當(dāng)d(u)=4時(shí)，有d(v)≥5。

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

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

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

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

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

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

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

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

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

情況1點(diǎn)v是假4-點(diǎn)

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

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

情況2點(diǎn)v是真4-點(diǎn)

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

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

如果v在GX中的鄰點(diǎn)有假點(diǎn)，則：

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

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

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

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

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

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

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

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

情況3點(diǎn)v是5-點(diǎn)

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

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

情況4面 f是4-面

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

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

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

情況5面 f是5+-面

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

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

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

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

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

此與式（5）矛盾。

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

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

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

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

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

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

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

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

4　結(jié)論

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

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

參考文獻(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].計(jì)算機(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ì)及其在無(wú)圈邊染色上的應(yīng)用[J].中國(guó)科學(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.