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

劉維嬋

LIU Weichan

西安電子科技大學 數學與統計學院，西安 710071

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

1　引言

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

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

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

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

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

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

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

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

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

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

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

考慮圖G的關聯平面圖GX，由于它是平面圖，故根據歐拉公式（1），有：

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

接下來，定義權轉移規則如下：

（R1）每個4-面向其關聯的假4-點轉移1/2。

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

（R3）每個4+-面向其關聯的5-點轉移1/3。

（R4）設 f是一個5+-面，v是其關聯的真4-點，如果v在 f的兩個相鄰點都是假4-點，則 f向v轉移7/6；否則，f向v轉移1。

（R5）每個5+-面向其關聯的假4-點轉移3/4。

設c*(v)與c*(f)為圖GX中的點v與面 f在執行完上述權轉移規則后的最終權值。

情況1點v是假4-點

如果點v關聯4個4+-面，則由（R1）與（R5）可知：

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

情況2點v是真4-點

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

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

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

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

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

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

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

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

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

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

（4）當v在GX中的鄰點中有4個假點時，則其關聯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}關聯的面。如果 5個面中至少有3個4+-面，則根據（R3）可得：

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

情況4面 f是4-面

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

若 f關聯恰好1個真4-點，則由前3條規則可得：

若 f不關聯真4-點，則由（R1）與（R3）可得：

情況5面 f是5+-面

當 d(f)=5時，則根據（R3）、（R4）與（R5）可知當 f關聯2個真4-點，2個假4-點與1個5-點時，f向外轉移的權值最多，從而：

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

最后，由于6+-點與3-面不參與權轉移，故它們的最終權值和初始權值相同，為非負。

至此，已經證明了圖GX中的所有點與面的最終權值均為非負，即得到：

由于權只在圖GX中的所有點與面的內部進行轉移，故轉移前后的總權值和不變，即根據式（3）有：

此與式（5）矛盾。

3　結論的推廣及其在定向染色中的應用

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

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

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

設G是一個簡單無向圖，現將圖G的每一條邊uv進行定向（令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-染色的最小整數k稱為圖的定向染色數，記為χo。設Θ(G)為對無向圖G進行定向后得到的所有可能的有向圖的集合，則無向圖G定向染色數定義為

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

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

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

4　結論

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

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

參考文獻：

[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].計算機工程與應用，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-平面圖的結構性質及其在無圈邊染色上的應用[J].中國科學：數學，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.