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

張董董，李永杰，劉 娟

（江西科技師范大學大數據科學學院，江西 南昌 330038）

1 前言

線性森林是每個連通分支都是路的圖。映射φ：E（G）→{1，2，…，k}被稱為線性k-染色，如果每個顏色類誘導一個線性森林。圖G 的線性蔭度，用la（G）表示，是使得G 有線性k-染色的最小整數k。這個概念是由Harary[1]提出的。1981 年，Akiyama，Exoo 和Harary[2]提出了以下著名的“線性蔭度猜想”：

對于Δ=3，4、Δ=5，6，8 和Δ=10 的圖，分別在文獻[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-平面嵌入且每個點至多關聯一條交叉邊，則稱為IC-平面圖。Fabrici 和Madaras[12]證明了每個1-平面圖G 滿足|E（G）|≤4|V（G）|-8，意味著δ（G）≤7，且構造了一個7-正則1-平面圖。Zhang 和Wu[13]證明了任意最大度Δ≥10 的1-平面圖是第一類圖。Wang、Liu 和Wang[14]證明了每一個Δ≥13 的1-平面圖G 滿足la（G）≥「Δ+1/2。黃丹君和姜楠[15]在2023年證明了Δ≥25 的1-平面圖G的線性蔭度為「Δ/2。

2 預備知識

本文考慮的圖都是簡單圖。對于圖G，用V（G）、E（G）、δ（G）和Δ（G）分別表示G 的頂點集、邊集、最小度和最大度。關聯平面圖G×是1-平面圖G 畫在平面上，V（G×）＝V（G）∪C（G），E（G×）＝E0（G）∪{xz，yx |xy∈E（G）E0（G）}。其中C（G）表示交叉點的集合，E0（G）表示非交叉邊的集合，z 是xy 上的交叉點。在G×中，若v∈V（G），則稱v 為真點；若v∈C（G），則稱v為假點。每個真點v 滿足，每個假點v滿足。設v∈V（G×）是一個真點。如果vv′∈E（G×）且v′是一個真點，稱v′是v 在G×中的一個直接鄰點。如果vw∈E（G×）且w 是一個假點滿足wv′∈E（G×）和vv′∈E（G），稱v′是v 在G×中的一個間接鄰點。設f∈F（G×）是一個3-面。若f 關聯了一個假點，稱f 是一個假3-面，否則稱為真3-面。令mi分別表示v 在G×中關聯i-面、i+-面、假3-面的個數。

對于v∈V（G），令E（v）表示在G 中與v 關聯的邊集合。給定一個k-線性染色φ，其中顏色集合為C={1，2，…，k}，令C（v）表示φ 在E（v）中使用的顏色集合。對于0≤i≤2，令Ii（v）={c∈C | c 恰好在E（v）中出現i 次}。若P=v1v2…vn中的所有邊都染了顏色c，則稱P 為G 中的（v1，vn）c-路。

引理2.1[13]設G 是一個1-平面圖，G×是其關聯平面圖。則下面結論成立：

（1）對于G×中的任意兩個假點u 和v，有uv?E（G×）；

（3）如果v 是G×中的一個3-點，v 關聯兩個3-面且v 在G×中與兩個假點相鄰，那么v 關聯了一個5+-面。

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

3 主要結論和證明過程

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

（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-圈。

證明：假設定理3.1 是錯的。設G 是一個連通的極小反例，G×是其關聯平面圖，滿足每條邊至多和其他邊交叉一次且交叉點盡可能少。則下列結論（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-點v∈V（G×），設v0，v1，…，vk-1表示在順時針方向下v 在G×中的鄰點，f0，f1，…，fk-1表示v 在G×中關聯的面，其中vvi，vvi+1∈?（fi），i=0，1，…，k-1，下標取模k。此外，如果vi是一個假點，那么假定vi是位于vui上的交叉點。

斷言1：設v 是一個大點，vi是一個假點，fi是一個假3-面。若ui，vi+1都是3-點，則ui，vi+1都是好3-點。

證明：根據（P4），很容易推斷出結果。

因為G 是連通圖，則G×也是連通圖。由歐拉公式|V（G×）|-|E（G×）|+|F（G×）|=2 和握手定理

可知有如下關系：

任意的x∈V（G×）∪F（G×），令c（x）=dG×（x）-4。則下面對x∈V（G×）∪F（G×）中各元素的權值進行調整，記調整后的權值為c′（x）。由于權只是在各元素內部進行轉移，從而權的總和保持不變。如能證明對于每一個x∈V（G×）∪F（G×），都有c′（x）≥0，可得到如下的矛盾

從而定理得證。

下面定義權轉移規則。

（R2）假設f 是一個5+-面，則f 均分給關聯的小點。

（R3）設v 是一個3-點。

設τ（v→vi），τ（v→fi）分別表示v 給vi，fi轉的權。

下面的斷言1 可以由（R1）-（R4）推斷得到。

所以下面考慮v∈V（G×）的情況。

情形5：k=7，則c（v）=3。由（P1）可知v 的每個鄰點（直接或間接）都是5+-點。根據（P2），若v 關聯了一個真3-面fi，則vi，vi+1都是6+-點且至多有一個-點。由（R1），v 至多給fi轉。因此，c′（v）≥

情形6：k=8，則c（v）=4。根據（P1），v 的每個鄰點（直接或間接）為4+-點。若v 需要給直接鄰點vi轉權時，則根據定義和（R1）-（R4），vi是一個4-點，vi+1是一個假點，fi=［vvivi+1］ 是一個假3-面，fi+1是一個4+-面，此時ui+1可能也是一個4-點。根據定義v 不再關聯其他鄰點需要v 轉權，則0。若v 需要給間接鄰點ui轉權時，除了前面類似的情況，還存在都是4+-面的情形，則否則，c′（v）≥

情形7：k=9，c（v）=5。根據（P1），v 的每個鄰點（直接或間接）為3+-點。

情形7.1：假設v 沒有間接鄰點。除了相鄰的3-點vi外，v 不用給其他鄰點轉權，根據（P2）和權規則可知，vvi關聯的都是4+-面。所以

情形7.2：假設v 有間接鄰點vi。設t 為v 相鄰的需要v 轉的3-點的個數。則根據定義，m3（v）≤kt-1。

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

情形8：k≥10，c（v）≥k-4。由（P1），v 的每個鄰點（直接或間接）為3+-點。

情形8.1：假設v 不存在間接鄰點。

情形8.2：假設v 存在間接鄰點vi。

情形8.2.1：fi-1，fi是4+-面。則v 至多給ui轉其他鄰點和情形8.1 類似討論可得：

情形8.2.3：fi-1，fi有一個3-面，一個4+-面，不失一般性，設fi-1是3-面，fi是4+-面。

假設vi-1是小點。若fi-2是4+-面，則討論類似，c′（v）≥0。所以下面考慮fi-2是3-面的情況，此時，vi-2是大點。若vi+1是大點，或fi+1是4+-面，則討論可得，φ=τ（v→vi-1）+τ（v→vi）+τ（v→vi+1）+τ（v→fi-1）+τ（v→fi）+τ（v→fi+1）≤因此，c′（v）≥0。否則，vi+1是小點且fi+1是3-面，vi+2是大點。若vi-1，ui，vi+1都是3-點，則很容易可以得到三個點都是好3-點，否則存在3-交錯4-圈。若vi-1，ui，vi+1中有兩個是3-點，則類似可得，至少有一個是好3-點。所以，與情形8.2.2 類似可知，ζ≤且c′（v）≥0。

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

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

證明：對邊數|E（G）|進行歸納證明。若|E（G）|≤5，則結果是平凡的，可以用不同的顏色給G 的所有邊染色。假設G 是一個IC-平面圖且|E（G）|≥6。若G 包含了一條邊xy 滿足dG（x）≤dG（y）且dG（x）≤2，則令H=G-xy。根據歸納假設，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。

假設δ（G）≥3。根據定理3.1，G 滿足下列結論之一：（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）可以和文獻[14]類似討論，因此，省略證明過程，在這里只討論條件（3）。

首先由條件2 可知dG（v）=dG（w）=dG（x）=9。令y表示u 除了w、v、x 之外的另一個鄰點?？紤]H=Guv，由歸納假設，運用顏色集合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 中的某種顏色。所以假設Δ=9且|S|=5，這意味著|C|=5 且C 中的每種顏色都至少在E（u）∪E（v）出現兩次，為了完成證明，根據對稱性考慮以下三種情況。

情形1：φ（uw）=1，φ（ux）=φ（uy）=2。

則3，4，5 恰好在E（v）出現兩次，1 至少在E（v）出現一次。

如果2∈I0（v），那么1∈I2（v）。假設φ（ux）=1 且H 中存在（u，x）1-路，則很容易可以推斷出2∈I1（u）。因此我們可以染uv 為1，改染ux 為2。假設φ（ux）≠1，或φ（ux）≠1 且H 中不存在（u，x）1-路，則我們可以染uv，vx 為2，改染ux 為φ（vx）。

假設2∈I1（v），則1∈I1（v）。如果H 中不存在（u，v）1-路，那么染uv 為1。假設a∈{3，4，5}∩（I0（x）∪I1（x））。如果H 中不存在（u，v）2-路，那么染uv 為2，改染ux 為c∈I1（x）中的某個顏色。否則，我們染uv為φ（vx），改染vx 為2，ux 為c∈I1（x）。假設{3，4，5}?I2（x）。如果φ（vx）=2，那么H 中存在（u，x）1-路。否則我們染ux 為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-路。在這種情況下，我們染uv 為φ（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）出現兩次，1 至少在E（v）出現一次。

假設2∈I0（v），那么1∈I2（v）。如果φ（ux）≠1，那么uv 染，vx 為2，改染ux 為φ（vx）。如果φ（wv）≠1，那么染uv，wv 為2，改染uw 為φ（vw）。假設φ（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-路至多存在一個，不妨設（u，v）1-路。所以，染uv 為1，改染wv 為2。

假設2∈I1（v），類似討論可以得到{3，4，5}?I2（v）且H 中存在（u，v）1-路。假設H 中不存在（w，v）2-路和（x，v）2-路，則很容易可以推斷出{1，3，4，5}?I2（w）。此時，我們染uv 為φ（wv），改染wv 為2。根據對稱性，假設H 中不存在（w，v）2-路，則染uv 為2，改染wu 為I1（w）。

情形3：φ（uw）=1，φ（ux）=2 且φ（uy）=3。

則4，5 恰好在E（v）出現兩次，1，2，3 至少在E（v）出現一次。

假設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-路至多存在一個，設，（u，w）3-路。因此，染uv 為2，改染uw 為3。

假設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 結論

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