最大度大于等于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 的情况仍没有被解决，还存在较大难度，仍需进一步的努力。