最大度大于等于9 的IC-平面圖的線性蔭度

張董董，李永杰，劉 娟

（江西科技師范大學(xué)大數(shù)據(jù)科學(xué)學(xué)院，江西 南昌 330038）

1 前言

線性森林是每個(gè)連通分支都是路的圖。映射φ：E（G）→{1，2，…，k}被稱為線性k-染色，如果每個(gè)顏色類誘導(dǎo)一個(gè)線性森林。圖G 的線性蔭度，用la（G）表示，是使得G 有線性k-染色的最小整數(shù)k。這個(gè)概念是由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]解決了。

若一個(gè)圖可以畫在歐幾里得平面上，使得每條邊沒有與其他的邊相交，則稱為平面圖。錢景和王維凡[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。

若一個(gè)圖可以畫在歐幾里得平面上，使得每條邊至多與一條邊相交，則稱為1-平面圖。若一個(gè)圖存在1-平面嵌入且每個(gè)點(diǎn)至多關(guān)聯(lián)一條交叉邊，則稱為IC-平面圖。Fabrici 和Madaras[12]證明了每個(gè)1-平面圖G 滿足|E（G）|≤4|V（G）|-8，意味著δ（G）≤7，且構(gòu)造了一個(gè)7-正則1-平面圖。Zhang 和Wu[13]證明了任意最大度Δ≥10 的1-平面圖是第一類圖。Wang、Liu 和Wang[14]證明了每一個(gè)Δ≥13 的1-平面圖G 滿足la（G）≥「Δ+1/2。黃丹君和姜楠[15]在2023年證明了Δ≥25 的1-平面圖G的線性蔭度為「Δ/2。

2 預(yù)備知識(shí)

本文考慮的圖都是簡單圖。對于圖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)。每個(gè)真點(diǎn)v 滿足，每個(gè)假點(diǎn)v滿足。設(shè)v∈V（G×）是一個(gè)真點(diǎn)。如果vv′∈E（G×）且v′是一個(gè)真點(diǎn)，稱v′是v 在G×中的一個(gè)直接鄰點(diǎn)。如果vw∈E（G×）且w 是一個(gè)假點(diǎn)滿足wv′∈E（G×）和vv′∈E（G），稱v′是v 在G×中的一個(gè)間接鄰點(diǎn)。設(shè)f∈F（G×）是一個(gè)3-面。若f 關(guān)聯(lián)了一個(gè)假點(diǎn)，稱f 是一個(gè)假3-面，否則稱為真3-面。令mi分別表示v 在G×中關(guān)聯(lián)i-面、i+-面、假3-面的個(gè)數(shù)。

對于v∈V（G），令E（v）表示在G 中與v 關(guān)聯(lián)的邊集合。給定一個(gè)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 是一個(gè)1-平面圖，G×是其關(guān)聯(lián)平面圖。則下面結(jié)論成立：

（1）對于G×中的任意兩個(gè)假點(diǎn)u 和v，有uv?E（G×）；

（3）如果v 是G×中的一個(gè)3-點(diǎn)，v 關(guān)聯(lián)兩個(gè)3-面且v 在G×中與兩個(gè)假點(diǎn)相鄰，那么v 關(guān)聯(lián)了一個(gè)5+-面。

引理2.2[13]若G 是Δ（G）≥10 的1-平面圖，則X′（G）=Δ（G），其中X′（G）表示G的邊色數(shù)。

3 主要結(jié)論和證明過程

定理3.1：若G 是Δ≥9 且δ≥3 的IC-平面圖，則下列結(jié)論之一成立：

（1）存在一條邊uv∈E（G），滿足dG（u）+dG（v）≤11；

（2）如果uv∈E（G）在某個(gè)3-圈上，那么dG（u）+dG（v）≤12；

（3）如果uv∈E（G）在兩個(gè)3-圈上，那么dG（u）=4；

（4）存在一個(gè)3-交錯(cuò)4-圈。

證明：假設(shè)定理3.1 是錯(cuò)的。設(shè)G 是一個(gè)連通的極小反例，G×是其關(guān)聯(lián)平面圖，滿足每條邊至多和其他邊交叉一次且交叉點(diǎn)盡可能少。則下列結(jié)論（P1）-（P4）成立：

（P1）每條邊uv∈E（G），滿足dG（u）+dG（v）≥12；

（P2）如果uv∈E（G）在某個(gè)3-圈上，那么dG（u）+dG（v）≥13；

（P3）如果uv∈E（G）在兩個(gè)3-圈上，則dG（u）≥5；

（P4）不存在一個(gè)3-交錯(cuò)4-圈。

對于一個(gè)k-點(diǎn)v∈V（G×），設(shè)v0，v1，…，vk-1表示在順時(shí)針方向下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是一個(gè)假點(diǎn)，那么假定vi是位于vui上的交叉點(diǎn)。

斷言1：設(shè)v 是一個(gè)大點(diǎn)，vi是一個(gè)假點(diǎn)，fi是一個(gè)假3-面。若ui，vi+1都是3-點(diǎn)，則ui，vi+1都是好3-點(diǎn)。

證明：根據(jù)（P4），很容易推斷出結(jié)果。

因?yàn)镚 是連通圖，則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)的總和保持不變。如能證明對于每一個(gè)x∈V（G×）∪F（G×），都有c′（x）≥0，可得到如下的矛盾

從而定理得證。

下面定義權(quán)轉(zhuǎn)移規(guī)則。

（R2）假設(shè)f 是一個(gè)5+-面，則f 均分給關(guān)聯(lián)的小點(diǎn)。

（R3）設(shè)v 是一個(gè)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 的每個(gè)鄰點(diǎn)（直接或間接）都是5+-點(diǎn)。根據(jù)（P2），若v 關(guān)聯(lián)了一個(gè)真3-面fi，則vi，vi+1都是6+-點(diǎn)且至多有一個(gè)-點(diǎn)。由（R1），v 至多給fi轉(zhuǎn)。因此，c′（v）≥

情形6：k=8，則c（v）=4。根據(jù)（P1），v 的每個(gè)鄰點(diǎn)（直接或間接）為4+-點(diǎn)。若v 需要給直接鄰點(diǎn)vi轉(zhuǎn)權(quán)時(shí)，則根據(jù)定義和（R1）-（R4），vi是一個(gè)4-點(diǎn)，vi+1是一個(gè)假點(diǎn)，fi=［vvivi+1］ 是一個(gè)假3-面，fi+1是一個(gè)4+-面，此時(shí)ui+1可能也是一個(gè)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)時(shí)，除了前面類似的情況，還存在都是4+-面的情形，則否則，c′（v）≥

情形7：k=9，c（v）=5。根據(jù)（P1），v 的每個(gè)鄰點(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)的個(gè)數(shù)。則根據(jù)定義，m3（v）≤kt-1。

若fi-1，fi有一個(gè)3-面，則不失一般性，設(shè)fi-1是3-面，fi是4+-面。若vi-1或ui是一個(gè)5+-點(diǎn)，或vi-1和ui都是4-點(diǎn)，或vi-1和ui一個(gè)是4-點(diǎn)且另一個(gè)是好3-點(diǎn)，則下面考慮vi-1，ui至少有一個(gè)壞3-點(diǎn)的情況。若vi-1是4-點(diǎn)且ui是一個(gè)壞3-點(diǎn)，則此時(shí)vi+1不是一個(gè)壞3-點(diǎn)且v 至多給vi+1轉(zhuǎn)，否則有3-交錯(cuò)4-圈。因此，c′（v）≥0。假設(shè)vi-1是3-點(diǎn)，則類似可得，vi+1不是一個(gè)壞3-點(diǎn)。若ui是一個(gè)4-點(diǎn)，則可得c′（v）≥0。若ui是一個(gè)3-點(diǎn)，則根據(jù)斷言1，vi-1和ui是好3-點(diǎn)

情形8：k≥10，c（v）≥k-4。由（P1），v 的每個(gè)鄰點(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有一個(gè)3-面，一個(gè)4+-面，不失一般性，設(shè)fi-1是3-面，fi是4+-面。

假設(shè)vi-1是小點(diǎn)。若fi-2是4+-面，則討論類似，c′（v）≥0。所以下面考慮fi-2是3-面的情況，此時(shí)，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)，則很容易可以得到三個(gè)點(diǎn)都是好3-點(diǎn)，否則存在3-交錯(cuò)4-圈。若vi-1，ui，vi+1中有兩個(gè)是3-點(diǎn)，則類似可得，至少有一個(gè)是好3-點(diǎn)。所以，與情形8.2.2 類似可知，ζ≤且c′（v）≥0。

由以上所有的情形可知，v∈V（G×），有c′（v）≥0，證明完畢。

定理3.2：設(shè)G 是一個(gè)Δ≥9 的IC-平面圖，則la（G）≤k，其中k=max{5，「（Δ+1）/2}。

證明：對邊數(shù)|E（G）|進(jìn)行歸納證明。若|E（G）|≤5，則結(jié)果是平凡的，可以用不同的顏色給G 的所有邊染色。假設(shè)G 是一個(gè)IC-平面圖且|E（G）|≥6。若G 包含了一條邊xy 滿足dG（x）≤dG（y）且dG（x）≤2，則令H=G-xy。根據(jù)歸納假設(shè)，H 有一個(gè)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Δ」。因?yàn)閨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）在某個(gè)3-圈上，則dG（u）+dG（v）≤12；（3）若uv∈E（G）在兩個(gè)3-圈上，則dG（u）=4；（4）存在一個(gè)3-交錯(cuò)4-圈。條件（1）、（2）和（4）可以和文獻(xiàn)[14]類似討論，因此，省略證明過程，在這里只討論條件（3）。

首先由條件2 可知dG（v）=dG（w）=dG（x）=9。令y表示u 除了w、v、x 之外的另一個(gè)鄰點(diǎn)?？紤]H=Guv，由歸納假設(shè)，運(yùn)用顏色集合C 使得H 有一個(gè)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è)顏色，將φ 延拓到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）中的某個(gè)顏色。否則，我們?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）。因?yàn)镠 中存在（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-路至多存在一個(gè)，不妨設(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）。此時(shí)，我們?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-路至多存在一個(gè)，設(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）。

4 結(jié)論

圖的線性蔭度問題是邊分解問題的一個(gè)子集，也是當(dāng)今圖論研究的一個(gè)熱點(diǎn)問題，得到了國內(nèi)外學(xué)者的廣泛關(guān)注。本文首先給出了一個(gè)關(guān)于IC-平面圖的輕結(jié)構(gòu)，然后圍繞所得到的輕結(jié)構(gòu)運(yùn)用線性染色的方法證明了IC-平面圖滿足線性蔭度猜想。但是目前IC-平面圖中Δ=7 的情況仍沒有被解決，還存在較大難度，仍需進(jìn)一步的努力。