外1-平面圖的均勻點蔭度

劉維嬋，張 欣

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

1 引言

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

本文僅考慮簡單的有限無向圖。設(shè)G是一個圖，用?(G),δ(G),V(G)與E(G)分別表示圖G的最大度，最小度，點集合與邊集合，用|G|與‖G ‖分別表示圖G的頂點數(shù)與邊數(shù)。

本文主要研究圖的均勻樹染色問題。所謂圖的均勻樹k-染色是一個從圖的點集合到數(shù)集{1,2,…,k}的映射 c，其滿足對于任何 1≤i≤j≤k，都有 |c-1(i)-c-1(j)|≤1，并且由點集c-1(i)導(dǎo)出的子圖為一個森林。使得圖G具有均勻樹k-染色的最小整數(shù)k稱為圖G的均勻點蔭度，記為va=(G)。例如，完全二部圖K9,9具有一個均勻樹2-染色（每一個部染一種顏色即可），而不具有均勻樹1-染色，從而va=( )K9,9=2。然而，容易驗證完全二部圖K9,9不具有均勻樹3-染色（如圖1的第一張圖所示），從而在研究圖的均勻樹染色的過程中，還需要定義一個染色參數(shù)，即圖的均勻點蔭度閥值。所謂圖G的均勻點蔭度閥值va*=(G)是一個盡可能小的整數(shù)k，其使得對于任何一個不小于k的整數(shù)t，圖G都具有均勻樹t-染色。例如，完全二部圖K9,9不具有均勻樹3-染色，但是對于每個不小于4的整數(shù)k都具有均勻樹k-染色（如圖1的第二張圖所示），從而va*=( )K9,9=4。顯而易見，對于任何圖G，都有va=(G)≤va*=(G)，并且va*=(G)與va=(G) 的差值可以很大。

圖1 K9,9的均勻樹染色

圖的均勻點蔭度的概念是由Wu，Zhang與Li[1]于2013年提出的，他們證明了va*=(G)≤3對于所有的圍長至少為5的平面圖成立，va*=(G)≤2對于所有的圍長至少為6的平面圖以及外平面圖成立等結(jié)論，同時提出了兩個猜想。

猜想1對于任何圖G,都有va*=(G)≤「(? (G )+1)/2」。

猜想2存在常數(shù)C，其使得對于任何平面圖G都有va*=(G )≤C。

到目前為止，猜想1（均勻點蔭度猜想）已被證明對于完全圖以及完全二部圖Kn,n[1]，最大度至少為|G|/2的圖[2]，最大度至多為3的圖[3]與5-退化圖[4]成立。猜想2則被Esperet，Lemoine與Maffray[5]于2015年解決，他們證明了va*=(G)≤4對于所有的平面圖G成立。由于Chartrand與Kronk[6]證明了平面圖的點蔭度至多為3，故Esperet，Lemoine與Maffray認(rèn)為考慮平面圖是否具有均勻樹3-染色是十分有意義的。

2015年，Zhang[7]證明了va*=(G)≤3對于任何兩個長度至多為4的圈都是點不交的平面圖以及圍長為4且任何兩個4-圈不相鄰的平面圖成立。將該結(jié)論與Wu，Zhang與Li所給出的前述關(guān)于平面圖的均勻點蔭度的結(jié)論結(jié)合起來，本文提出如下猜想：

猜想3對于任何平面圖G，都有va*=(G )≤3。

如果一個圖G可以畫在一個平面上，使得其所有頂點都分布在G的外面上，并且每條邊最多被交叉一次，則稱圖G為外1-平面圖。從這個定義容易看出，每個外1-平面圖都是平面圖。因此，下文將針對外1-平面圖證明猜想3，繼而對外1-平面圖證明猜想1。

2 外1-平面圖的結(jié)構(gòu)

關(guān)于圖的結(jié)構(gòu)問題的研究是圖論領(lǐng)域的一個熱門研究方向，在該領(lǐng)域有很多結(jié)果，并且有一部分被用于圖的染色問題的研究，讀者可參閱文獻[8-15]了解相關(guān)細(xì)節(jié)。

本章將主要討論外1-平面圖的結(jié)構(gòu)，然后在第3章將其用于研究外1-平面圖的相關(guān)染色問題。

設(shè)G是外1-平面圖，并且其已經(jīng)畫在平面上，使得其所有的頂點v1,v2,…,v|G|都按照該次序以逆時針順序分布在G的外面上，并且每條邊最多被交叉一次。按如此方式畫好的外1-平面圖稱為外1-平圖。記V[vi,vj]={vi,vi+1,…,vj}，V(vi,vj)=V[vi,vj]{vi,vj}，分別用G[vi,vj],G(vi,vj)表示由點集V[vi,vj],V(vi,vj)導(dǎo)出的子圖。如果vivj∈E(G)并且 | j-i|≠1,| G |-1，則稱vivj為外1-平圖G的一條弦。本章首先證明如下一個結(jié)構(gòu)引理。

引理1設(shè)圖G是一個2-連通的外1-平面圖，則圖G含有以下四種結(jié)構(gòu)之一：

（1）邊uv，其中d(u)=2,d(v)≤3；

（2）長度為3的圈uvwu，其中d(u)=2；

（3）長度為4的圈uxvyu，其中d(u)=d(v)=2；

（4）長度為4的圈uxvyu，其中d(u)=d(v)=3,uv∈E(G)。

此外，如果圖G含有結(jié)構(gòu)（3）或者結(jié)構(gòu)（4），則按如下方式得到的圖H依然是外1-平面圖：先將點u刪除，此時若xy?E(G)，則將x與y用一條新邊連接。

證明 不妨假設(shè)圖G是一個外1-平圖，且不含有上述四種結(jié)構(gòu)之一。如果圖G不含有交叉弦，則其為外平面圖，而眾所周知的是每個外平面圖必定含有一條邊uv，其中d(u)=2,d(v)≤3，從而G 包含結(jié)構(gòu)（1）。

設(shè)弦vivj與弦vkvl在圖G中交叉，其中1≤i＜k＜j＜l，并且G[vi,vl]僅含有兩條交叉弦，即vivj與vkvl。如果 k-i≥3，則G[vi,vk]中必定含有弦，否則根據(jù)圖G的2-連通性可推出子圖G(vi,vk)是一條路。由于|V(vi,vk)|=k-i-1≥2，故在V(vi,vk)中必定含有兩個相鄰的度數(shù)為2的點，因此圖G含有結(jié)構(gòu)（1）。另一方面，如果G[vi,vk]中含有弦，則取其中的一條弦vsvt，使得 i≤s＜t≤k并且G[vs,vt]只包含一條弦，即vsvt。此時，再次根據(jù)圖G的2-連通性又可推出t-s=2且 vsvs+1,vs+1vt∈E(G)，從而 vsvs+1vtvs是一個長度為3的圈，并且d(vs+1)=2，于是圖G含有結(jié)構(gòu)（2）。因此，k-i≤2。同理可證，l-j≤2,j-k≤2。

如果k-i=2,則必定有d(vk-1)=2,vk-1vk∈E(G)。如果d(vk)≤3，則圖G 含有結(jié)構(gòu)（1）。如果d(vk)≥4，則必定有 vivk∈E(G)或者 vkvj∈E(G)。此時若vivk∈E(G)，則 vivk-1vkvi是一個長度為3的圈，并且d(vk-1)=2。若vkvj∈E(G)，則vkvj-1vjvk是一個長度為3的圈，并且d(vj-1)=2。無論何種情況，均可推出圖G含有結(jié)構(gòu)（2）。因此，k-i=1。此時如果vivk?E(G)，則點vl是圖G的一個割點，此與圖的2-連通性矛盾，因此有vivk∈E(G)。

同理可證l-j=1且vjvl∈E(G)。此時若 j-k=2,則 d(vk+1)=2,vkvk+1∈E(G)。如果 d(vk)≤3，則圖 G含有結(jié)構(gòu)（1）。如果d(vk)≥4，則vkvk+1vjvk是一個長度為3的圈，從而圖G含有結(jié)構(gòu)（2）。因此，j-k=1。此時如果vkvj?E(G)，則vkvlvjvivk是一個長度為4的圈，并且d(vk)=d(vj)=2，于是圖G含有結(jié)構(gòu)（3）。如果vkvj∈E(G)，則vkvlvjvivk是一個長度為4的圈，并且d(vk)=d(vj)=3,vkvj∈E(G)，于是圖 G 含有結(jié)構(gòu)（4）。無論上述何種情況，均可驗證G-vk+vivl依然是外1-平面圖。

3 外1-平面圖的染色

本章首先考慮與圖的樹染色密切相關(guān)的無圈點染色。圖的無圈點k-染色是圖的一個正常的點k-染色，其使得任何兩個色類的導(dǎo)出子圖是一個森林。使得圖G具有無圈點k-染色的最小整數(shù)k稱為圖G的無圈點色數(shù)，記為χa(G)。Borodin[8]證明了每個平面圖的無圈點色數(shù)至多為5，并且這個上界5是緊的。下面考慮外1-平面圖的無圈點染色問題。

定理1如果G是外1-平面圖，則χa(G)≤4。

證明 假如該結(jié)論不成立，則取G為該定理的極小反例，即 χa(G)＞4，且對于任何圖H，只要 | H|+‖H‖＜| G |+‖G ‖ ，則 χa(H)≤4。顯然，圖 H 是2-連通的。由引理1，圖H包含引理所述的四種結(jié)構(gòu)之一。

情況1圖H包含邊uv，其中d(u)=2,d(v)≤3。

此時，不妨設(shè)d(v)=3。記u的另外一個鄰點為w，v的另外兩個鄰點為v1與v2。由圖H的極小性可知圖 H′=H-u具有一個無圈點4-染色c。如果c(v)≠c(w)，則用顏色 c(u)∈{1,2,3,4}/{c(v),c(w)}染點u。如果c(v)=c(w)，則用顏色c(u)∈{1,2,3,4}/{c(v),c(v1),c(v2)}染點u。無論上述何種情況均可得到圖G的一個無圈點4-染色，矛盾。

情況2圖H包含長度為3的圈uvwu,其中d(u)=2。

由圖H的極小性可知圖H′=H-u具有一個無圈點4-染色c。此時用顏色c(u)∈{1,2,3,4}/{c(v),c(w)}染點u即可得到圖G的一個無圈點4-染色，矛盾。

情況3圖H包含長度為4的圈uxvyu，其中d(u)=d(v)=2。

由引理1與圖H的極小性可知圖H′=H-u+xy具有一個無圈點4-染色c。此時用顏色c(u)∈{1,2,3,4}/{c(x),c(y)}染點u即可得到圖G的一個無圈點4-染色，矛盾。

情況4圖H包含長度為4的圈uxvyu，其中d(u)=d(v)=3,uv∈E(G)。

由引理1與圖H的極小性可知圖H′=H-u+xy具有一個無圈點4-染色c。此時用顏色c(u)∈{1,2,3,4}/{c(x),c(y),c(v)}染點u即可得到圖G的一個無圈點4-染色，矛盾。

綜上所述，該定理的極小反例不存在，從而結(jié)論成立。

注1由定理1給出的外1-平面圖的無圈點色數(shù)的上界4是緊的，例如完全圖K4是一個外1-平面圖，其無圈點色數(shù)恰好是4。

定理2如果G是外1-平面圖，則va*=(G )≤3。

證明 由于每個平面圖的均勻點蔭度閥值至多為4[5]，故此處僅需證圖G具有均勻樹3-染色。由定理1，可以用四種顏色對圖G進行染色，即將圖G的點集合分成四個兩兩不交的子集V1,V2,V3,V4，使得由任何兩個子集導(dǎo)出的子圖是森林。不妨假設(shè)|V1|≤|G|/4。由于

故 必 定存在 i∈{2,3,4}，使 得 | V1|+| Vi|≥|G|/3+2|V1|/3。因此，不妨設(shè) |V1|+| V2|≥|G|/3+2|V1|/3，從而 |V2|≥|G|/3-|V1|/3。于是可以取到V2的一個大小為 「|G|/3」-|V1|的子集V，使得S1:=V1∪V的導(dǎo)出子圖是森林，并且|S1|=「|G|/3」。

下面考慮集合U2:=V2VU3:=V3,U4:=V4。由于 |U2|+| U3|+| U4|=| G |-| S1|≥2|G|/3，故不妨假設(shè)|U2|≤2|G|/9。由于

故必定存在i∈{3,4},使得 |U2|+| Ui|≥|G|/3+|U2|/2。因此，不妨設(shè) | U2|+| U3|≥|G|/3+|U2|/2，從而 | U3|≥|G|/3-|U2|/2。于是可以取到U3的一個大小為「|G|/3」-|U2|的子集U，使得S2:=U2∪U的導(dǎo)出子圖是森林，并且|S2|=「|G|/3」。

最后，令 S3:=V(G)(S1∪S2)，則 S3?V3∪V4。從而S3的導(dǎo)出子圖是森林，并且 「|G|/3」≤|S3|≤「|G|/3」。

因此，圖G具有均勻樹3-染色，其三個色類分別為S1,S2,S3。

注2定理2的證明過程說明，只要事先給出了外1-平面圖的無圈點4-染色，則必定可以在多項式時間內(nèi)構(gòu)造出它的均勻樹3-染色。

4 結(jié)論

設(shè)G是外1-平面圖，如果Δ(G)≥4，則由定理2知va*=(G )≤3≤「(? ( G)+1)/2」。如果2≤Δ(G)≤3，則由于Zhang在文獻[3]中證明了任何最大度至多為3的圖都有va*=(G )≤2，故依然有va*=(G)≤「(? ( G)+1)/2」。如果Δ(G)≤1，則圖G本身就是一個樹，從而va*=(G)=1=「(? (G )+1)/2」。因此得到：

結(jié)論1猜想1對于外1-平面圖成立。

另一方面，由于外1-平面圖一定是平面圖，故由定理2立刻可以推出。

結(jié)論2猜想3對于外1-平面圖成立。

：

[1]Wu J L，Zhang X，Li H.Equitable vertex arboricity of graphs[J].Discrete Math，2013，313：2696-2701.

[2]Zhang X，Wu J L.A conjecture on equitable vertex arboricity of graphs[J].Filomat，2014，28（1）：217-219.

[3]Zhang X.Equitable vertex arboricity of subcubic graphs[J].Discrete Math，2016，339：1724-1726.

[4]Chen G，Gao Y，Shan S，et al.Equitable vertex arboricity of 5-degenerate graphs[J].J Comb Optim，2017，34（2）.

[5]Esperet L，Lemoine L，Maffray F.Equitable partition of graphs into induced forests[J].Discrete Math，2015，338（8）：1481-1483.

[6]Chartrand G，Kronk H V.The point-arboricity of planar graphs[J].J Lond Math Soc，1969，44：612-616.

[7]Zhang X.Equitable vertex arboricity of planar graphs[J].Discrete Mathematics，2015（1）：2696-2701.

[8]Borodin O V.On acyclic coloring of planar graphs[J].Discrete Math，1979，25：211-236.

[9]Zhang X，Drawing complete multipartite graphs on the plane with restrictions on crossings[J].Acta Math Sin：Engl Ser，2014，30（12）：2045-2053.

[10]Zhang X.On equitable colorings of sparse graphs[J].Bull Malays Math Sci Soc，2016，39（1）：257-268.

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

[12]張欣，劉桂真，吳建良.不含3-圈的1-平面圖的邊染色[J].山東大學(xué)學(xué)報：理學(xué)版，2010，45（6）：15-17.

[13]張欣，徐蘭，劉桂真.稀疏圖的k-森林染色[J].山東大學(xué)學(xué)報：理學(xué)版，2011，46（4）：1-3.

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

[15]劉維嬋，NIC-平面圖的輕邊存在性及其在定向染色中的應(yīng)用[J].計算機工程與應(yīng)用，2018，54（7）：62-65.