張董董,李永杰,劉 娟
(江西科技師范大學(xué)大數(shù)據(jù)科學(xué)學(xué)院,江西 南昌 330038)
線性森林是每個連通分支都是路的圖。映射φ:E(G)→{1,2,…,k}被稱為線性k-染色,如果每個顏色類誘導(dǎo)一個線性森林。圖G 的線性蔭度,用la(G)表示,是使得G 有線性k-染色的最小整數(shù)k。這個概念是由Harary[1]提出的。1981 年,Akiyama,Exoo 和Harary[2]提出了以下著名的“線性蔭度猜想”:
對于Δ=3,4、Δ=5,6,8 和Δ=10 的圖,分別在文獻(xiàn)[2],[3],[4],[5]被證明猜想1 成立。對于平面圖,Wu[6]首先證明了Δ≠7 的情形滿足猜想1;接著剩余的情況Δ=7 被Wu 等[7]解決了。
若一個圖可以畫在歐幾里得平面上,使得每條邊沒有與其他的邊相交,則稱為平面圖。錢景和王維凡[8]在2005 年證明了若G 為不含4-圈的平面圖,則la2(G)≤「(Δ+1)2+3。常晶晶和徐常青[9]在2014年證明了若G 為不含弦6-圈的平面圖,則la2(G)≤「Δ/2+6。徐常青,安麗莎和杜亞濤[10]在2014 年得到了平面圖線性2-蔭度的上界,證明了:若Δ=0,3(mod 4),則la2(G)≤「Δ/2+8;若Δ≡1,2(mod 4),則la2(G)≤「Δ/2+7。2019 年,陳宏宇和譚香[11]證明了,若G 為不含5-圈和相鄰4-圈的平面圖,則la2(G)≤「Δ/2+4。
若一個圖可以畫在歐幾里得平面上,使得每條邊至多與一條邊相交,則稱為1-平面圖。若一個圖存在1-平面嵌入且每個點(diǎn)至多關(guān)聯(lián)一條交叉邊,則稱為IC-平面圖。Fabrici 和Madaras[12]證明了每個1-平面圖G 滿足|E(G)|≤4|V(G)|-8,意味著δ(G)≤7,且構(gòu)造了一個7-正則1-平面圖。Zhang 和Wu[13]證明了任意最大度Δ≥10 的1-平面圖是第一類圖。Wang、Liu 和Wang[14]證明了每一個Δ≥13 的1-平面圖G 滿足la(G)≥「Δ+1/2。黃丹君和姜楠[15]在2023年證明了Δ≥25 的1-平面圖G的線性蔭度為「Δ/2。
本文考慮的圖都是簡單圖。對于圖G,用V(G)、E(G)、δ(G)和Δ(G)分別表示G 的頂點(diǎn)集、邊集、最小度和最大度。關(guān)聯(lián)平面圖G×是1-平面圖G 畫在平面上,V(G×)=V(G)∪C(G),E(G×)=E0(G)∪{xz,yx |xy∈E(G)E0(G)}。其中C(G)表示交叉點(diǎn)的集合,E0(G)表示非交叉邊的集合,z 是xy 上的交叉點(diǎn)。在G×中,若v∈V(G),則稱v 為真點(diǎn);若v∈C(G),則稱v為假點(diǎn)。每個真點(diǎn)v 滿足,每個假點(diǎn)v滿足。設(shè)v∈V(G×)是一個真點(diǎn)。如果vv′∈E(G×)且v′是一個真點(diǎn),稱v′是v 在G×中的一個直接鄰點(diǎn)。如果vw∈E(G×)且w 是一個假點(diǎn)滿足wv′∈E(G×)和vv′∈E(G),稱v′是v 在G×中的一個間接鄰點(diǎn)。設(shè)f∈F(G×)是一個3-面。若f 關(guān)聯(lián)了一個假點(diǎn),稱f 是一個假3-面,否則稱為真3-面。令mi分別表示v 在G×中關(guān)聯(lián)i-面、i+-面、假3-面的個數(shù)。
對于v∈V(G),令E(v)表示在G 中與v 關(guān)聯(lián)的邊集合。給定一個k-線性染色φ,其中顏色集合為C={1,2,…,k},令C(v)表示φ 在E(v)中使用的顏色集合。對于0≤i≤2,令I(lǐng)i(v)={c∈C | c 恰好在E(v)中出現(xiàn)i 次}。若P=v1v2…vn中的所有邊都染了顏色c,則稱P 為G 中的(v1,vn)c-路。
引理2.1[13]設(shè)G 是一個1-平面圖,G×是其關(guān)聯(lián)平面圖。則下面結(jié)論成立:
(1)對于G×中的任意兩個假點(diǎn)u 和v,有uv?E(G×);
(3)如果v 是G×中的一個3-點(diǎn),v 關(guān)聯(lián)兩個3-面且v 在G×中與兩個假點(diǎn)相鄰,那么v 關(guān)聯(lián)了一個5+-面。
引理2.2[13]若G 是Δ(G)≥10 的1-平面圖,則X′(G)=Δ(G),其中X′(G)表示G的邊色數(shù)。
定理3.1:若G 是Δ≥9 且δ≥3 的IC-平面圖,則下列結(jié)論之一成立:
(1)存在一條邊uv∈E(G),滿足dG(u)+dG(v)≤11;
(2)如果uv∈E(G)在某個3-圈上,那么dG(u)+dG(v)≤12;
(3)如果uv∈E(G)在兩個3-圈上,那么dG(u)=4;
(4)存在一個3-交錯4-圈。
證明:假設(shè)定理3.1 是錯的。設(shè)G 是一個連通的極小反例,G×是其關(guān)聯(lián)平面圖,滿足每條邊至多和其他邊交叉一次且交叉點(diǎn)盡可能少。則下列結(jié)論(P1)-(P4)成立:
(P1)每條邊uv∈E(G),滿足dG(u)+dG(v)≥12;
(P2)如果uv∈E(G)在某個3-圈上,那么dG(u)+dG(v)≥13;
(P3)如果uv∈E(G)在兩個3-圈上,則dG(u)≥5;
(P4)不存在一個3-交錯4-圈。
對于一個k-點(diǎn)v∈V(G×),設(shè)v0,v1,…,vk-1表示在順時針方向下v 在G×中的鄰點(diǎn),f0,f1,…,fk-1表示v 在G×中關(guān)聯(lián)的面,其中vvi,vvi+1∈?(fi),i=0,1,…,k-1,下標(biāo)取模k。此外,如果vi是一個假點(diǎn),那么假定vi是位于vui上的交叉點(diǎn)。
斷言1:設(shè)v 是一個大點(diǎn),vi是一個假點(diǎn),fi是一個假3-面。若ui,vi+1都是3-點(diǎn),則ui,vi+1都是好3-點(diǎn)。
證明:根據(jù)(P4),很容易推斷出結(jié)果。
因為G 是連通圖,則G×也是連通圖。由歐拉公式|V(G×)|-|E(G×)|+|F(G×)|=2 和握手定理
可知有如下關(guān)系:
任意的x∈V(G×)∪F(G×),令c(x)=dG×(x)-4。則下面對x∈V(G×)∪F(G×)中各元素的權(quán)值進(jìn)行調(diào)整,記調(diào)整后的權(quán)值為c′(x)。由于權(quán)只是在各元素內(nèi)部進(jìn)行轉(zhuǎn)移,從而權(quán)的總和保持不變。如能證明對于每一個x∈V(G×)∪F(G×),都有c′(x)≥0,可得到如下的矛盾
從而定理得證。
下面定義權(quán)轉(zhuǎn)移規(guī)則。
(R2)假設(shè)f 是一個5+-面,則f 均分給關(guān)聯(lián)的小點(diǎn)。
(R3)設(shè)v 是一個3-點(diǎn)。
設(shè)τ(v→vi),τ(v→fi)分別表示v 給vi,fi轉(zhuǎn)的權(quán)。
下面的斷言1 可以由(R1)-(R4)推斷得到。
所以下面考慮v∈V(G×)的情況。
情形5:k=7,則c(v)=3。由(P1)可知v 的每個鄰點(diǎn)(直接或間接)都是5+-點(diǎn)。根據(jù)(P2),若v 關(guān)聯(lián)了一個真3-面fi,則vi,vi+1都是6+-點(diǎn)且至多有一個-點(diǎn)。由(R1),v 至多給fi轉(zhuǎn)。因此,c′(v)≥
情形6:k=8,則c(v)=4。根據(jù)(P1),v 的每個鄰點(diǎn)(直接或間接)為4+-點(diǎn)。若v 需要給直接鄰點(diǎn)vi轉(zhuǎn)權(quán)時,則根據(jù)定義和(R1)-(R4),vi是一個4-點(diǎn),vi+1是一個假點(diǎn),fi=[vvivi+1] 是一個假3-面,fi+1是一個4+-面,此時ui+1可能也是一個4-點(diǎn)。根據(jù)定義v 不再關(guān)聯(lián)其他鄰點(diǎn)需要v 轉(zhuǎn)權(quán),則0。若v 需要給間接鄰點(diǎn)ui轉(zhuǎn)權(quán)時,除了前面類似的情況,還存在都是4+-面的情形,則否則,c′(v)≥
情形7:k=9,c(v)=5。根據(jù)(P1),v 的每個鄰點(diǎn)(直接或間接)為3+-點(diǎn)。
情形7.1:假設(shè)v 沒有間接鄰點(diǎn)。除了相鄰的3-點(diǎn)vi外,v 不用給其他鄰點(diǎn)轉(zhuǎn)權(quán),根據(jù)(P2)和權(quán)規(guī)則可知,vvi關(guān)聯(lián)的都是4+-面。所以
情形7.2:假設(shè)v 有間接鄰點(diǎn)vi。設(shè)t 為v 相鄰的需要v 轉(zhuǎn)的3-點(diǎn)的個數(shù)。則根據(jù)定義,m3(v)≤kt-1。
若fi-1,fi有一個3-面,則不失一般性,設(shè)fi-1是3-面,fi是4+-面。若vi-1或ui是一個5+-點(diǎn),或vi-1和ui都是4-點(diǎn),或vi-1和ui一個是4-點(diǎn)且另一個是好3-點(diǎn),則下面考慮vi-1,ui至少有一個壞3-點(diǎn)的情況。若vi-1是4-點(diǎn)且ui是一個壞3-點(diǎn),則此時vi+1不是一個壞3-點(diǎn)且v 至多給vi+1轉(zhuǎn),否則有3-交錯4-圈。因此,c′(v)≥0。假設(shè)vi-1是3-點(diǎn),則類似可得,vi+1不是一個壞3-點(diǎn)。若ui是一個4-點(diǎn),則可得c′(v)≥0。若ui是一個3-點(diǎn),則根據(jù)斷言1,vi-1和ui是好3-點(diǎn)
情形8:k≥10,c(v)≥k-4。由(P1),v 的每個鄰點(diǎn)(直接或間接)為3+-點(diǎn)。
情形8.1:假設(shè)v 不存在間接鄰點(diǎn)。
情形8.2:假設(shè)v 存在間接鄰點(diǎn)vi。
情形8.2.1:fi-1,fi是4+-面。則v 至多給ui轉(zhuǎn)其他鄰點(diǎn)和情形8.1 類似討論可得:
情形8.2.3:fi-1,fi有一個3-面,一個4+-面,不失一般性,設(shè)fi-1是3-面,fi是4+-面。
假設(shè)vi-1是小點(diǎn)。若fi-2是4+-面,則討論類似,c′(v)≥0。所以下面考慮fi-2是3-面的情況,此時,vi-2是大點(diǎn)。若vi+1是大點(diǎn),或fi+1是4+-面,則討論可得,φ=τ(v→vi-1)+τ(v→vi)+τ(v→vi+1)+τ(v→fi-1)+τ(v→fi)+τ(v→fi+1)≤因此,c′(v)≥0。否則,vi+1是小點(diǎn)且fi+1是3-面,vi+2是大點(diǎn)。若vi-1,ui,vi+1都是3-點(diǎn),則很容易可以得到三個點(diǎn)都是好3-點(diǎn),否則存在3-交錯4-圈。若vi-1,ui,vi+1中有兩個是3-點(diǎn),則類似可得,至少有一個是好3-點(diǎn)。所以,與情形8.2.2 類似可知,ζ≤且c′(v)≥0。
由以上所有的情形可知,v∈V(G×),有c′(v)≥0,證明完畢。
定理3.2:設(shè)G 是一個Δ≥9 的IC-平面圖,則la(G)≤k,其中k=max{5,「(Δ+1)/2}。
證明:對邊數(shù)|E(G)|進(jìn)行歸納證明。若|E(G)|≤5,則結(jié)果是平凡的,可以用不同的顏色給G 的所有邊染色。假設(shè)G 是一個IC-平面圖且|E(G)|≥6。若G 包含了一條邊xy 滿足dG(x)≤dG(y)且dG(x)≤2,則令H=G-xy。根據(jù)歸納假設(shè),H 有一個k-線性染色φ 且使用的色集合為C={1,2,…,k}。令S=I2(y)∪(I1(x)∩I1(y))。則|S|=|I2(y)∪(I1(x)∩I1(y))|≤1/2(dH(x)+dH(y))」=-1/2(dG(x)+dG(y))」-1≤1/2Δ」。因為|C|≥「(Δ+1)/2,所以存在一種顏色a∈CS,可以染xy 為a,將φ 延拓到G。
假設(shè)δ(G)≥3。根據(jù)定理3.1,G 滿足下列結(jié)論之一:(1)存在一條邊uv∈E(G),滿足dG(u)+dG(v)≤11;(2)若uv∈E(G)在某個3-圈上,則dG(u)+dG(v)≤12;(3)若uv∈E(G)在兩個3-圈上,則dG(u)=4;(4)存在一個3-交錯4-圈。條件(1)、(2)和(4)可以和文獻(xiàn)[14]類似討論,因此,省略證明過程,在這里只討論條件(3)。
首先由條件2 可知dG(v)=dG(w)=dG(x)=9。令y表示u 除了w、v、x 之外的另一個鄰點(diǎn)。考慮H=Guv,由歸納假設(shè),運(yùn)用顏色集合C 使得H 有一個k-線性染色φ。令S=I2(u)∪I2(v)∪(I1(u)∩I1(v))。則類似證明可得|S|≤|I2(u)∪I2(v)∪(I1(u)∩I1(v))|≤5。如果|S|≤4,那么可以染uv 為中CS 的某個顏色,將φ 延拓到G。如果Δ≥10,那么很容易推斷出|C|≥6,可以染uv 為CS 中的某種顏色。所以假設(shè)Δ=9且|S|=5,這意味著|C|=5 且C 中的每種顏色都至少在E(u)∪E(v)出現(xiàn)兩次,為了完成證明,根據(jù)對稱性考慮以下三種情況。
情形1:φ(uw)=1,φ(ux)=φ(uy)=2。
則3,4,5 恰好在E(v)出現(xiàn)兩次,1 至少在E(v)出現(xiàn)一次。
如果2∈I0(v),那么1∈I2(v)。假設(shè)φ(ux)=1 且H 中存在(u,x)1-路,則很容易可以推斷出2∈I1(u)。因此我們可以染uv 為1,改染ux 為2。假設(shè)φ(ux)≠1,或φ(ux)≠1 且H 中不存在(u,x)1-路,則我們可以染uv,vx 為2,改染ux 為φ(vx)。
假設(shè)2∈I1(v),則1∈I1(v)。如果H 中不存在(u,v)1-路,那么染uv 為1。假設(shè)a∈{3,4,5}∩(I0(x)∪I1(x))。如果H 中不存在(u,v)2-路,那么染uv 為2,改染ux 為c∈I1(x)中的某個顏色。否則,我們?nèi)緐v為φ(vx),改染vx 為2,ux 為c∈I1(x)。假設(shè){3,4,5}?I2(x)。如果φ(vx)=2,那么H 中存在(u,x)1-路。否則我們?nèi)緐x 為1,改染uv 為2。如果φ(vx)=a 且a∈{3,4,5}∩(I0(x)∪I1(x)),那么ux 染為a,改染ux 為a,vx 為c∈I1(x)。如果φ(vx)=1,則1∈I2(x)且2∈I1(x)。如果H 中不存在(u,v)2-路,那么uv 染為1,改染vx 為2。否則,如果φ(vw)≠2,那么很容易可以推斷出2∈I1(w)。因為H 中存在(u,v)2-路,那么H 中不存在(u,w)2-路。在這種情況下,我們?nèi)緐v 為φ(vw),改染vw 為2。否則,如果φ(vw)=2,則a∈{3,4,5}∩(I0(w)∪I1(w))。因此,染uv 為1,改染vw 為a。
情形2:φ(uy)=2,φ(ux)=φ(uw)=2。
則3,4,5 恰好在E(v)出現(xiàn)兩次,1 至少在E(v)出現(xiàn)一次。
假設(shè)2∈I0(v),那么1∈I2(v)。如果φ(ux)≠1,那么uv 染,vx 為2,改染ux 為φ(vx)。如果φ(wv)≠1,那么染uv,wv 為2,改染uw 為φ(vw)。假設(shè)φ(wv)=φ(vx)=1,則很容易推斷出{3,4,5}?I2(w),{3,4,5}?I2(x)。如果1∈I1(w),那么染uv,wv 為2,改染uw 為1。如果1∈I1(x),那么類似討論。因此,{2}=I1(x)=I1(w)。并且H 中(u,v)1-路和(u,w)1-路至多存在一個,不妨設(shè)(u,v)1-路。所以,染uv 為1,改染wv 為2。
假設(shè)2∈I1(v),類似討論可以得到{3,4,5}?I2(v)且H 中存在(u,v)1-路。假設(shè)H 中不存在(w,v)2-路和(x,v)2-路,則很容易可以推斷出{1,3,4,5}?I2(w)。此時,我們?nèi)緐v 為φ(wv),改染wv 為2。根據(jù)對稱性,假設(shè)H 中不存在(w,v)2-路,則染uv 為2,改染wu 為I1(w)。
情形3:φ(uw)=1,φ(ux)=2 且φ(uy)=3。
則4,5 恰好在E(v)出現(xiàn)兩次,1,2,3 至少在E(v)出現(xiàn)一次。
假設(shè)3∈I2(v)。則可得H 中存在(u,v)1-路和(u,v)2-路,否則染uv 為1 或2。如果a∈{4,5}∩(I0(w)∪I1(w)),那么染uv 為1,改染uw 為2。類似討論,可得3∈I2(v),且H 中(u,w)3-路和(u,x)3-路至多存在一個,設(shè),(u,w)3-路。因此,染uv 為2,改染uw 為3。
假設(shè)1∈I2(v)(2∈I2(v)可以類似討論)。則可得H 中存在(u,v)2-路和(u,v)3-路,否則染uv 為2 或3。類似討論,可以得到1∈I1(v)。因此,染uv 為2,改染ux 為1,uw 為I1(w)。
圖的線性蔭度問題是邊分解問題的一個子集,也是當(dāng)今圖論研究的一個熱點(diǎn)問題,得到了國內(nèi)外學(xué)者的廣泛關(guān)注。本文首先給出了一個關(guān)于IC-平面圖的輕結(jié)構(gòu),然后圍繞所得到的輕結(jié)構(gòu)運(yùn)用線性染色的方法證明了IC-平面圖滿足線性蔭度猜想。但是目前IC-平面圖中Δ=7 的情況仍沒有被解決,還存在較大難度,仍需進(jìn)一步的努力。