不含相交3圈和相邻4-圈的平面图是(2, 2, 0)-可染的

毛惠群

(浙江师范大学数学系， 浙江金华 321004)

1 引言

本文考虑的图都是简单无向图.G=(V,E)是一个以V为顶点集、E为边集的图.G的一个(c1,c2, …,ck)-染色是一个映射φ：V︳→{1, 2, …,k}， 使得对每一个i∈{1, 2, …,k}， 子图G[Vi]的最大度至多为ci， 其中Vi={v∈V|φ(Vi)=i}.运用这个概念， 著名的四色定理[1]可表述为： 每一个平面图是(0, 0, 0, 0)-可染的；Eaton[2]和Hull证明了每个平面图是(2, 2, 2)-可染的.Grötzsch[3]的三色定理为： 每个不含三角形的平面图是(0, 0, 0)-可染的.Steinberg猜想[4]为: 每个既没有4圈又没有5圈的平面图是(0, 0, 0)-可染的. 根据Steinberg猜想， 已取得一些结果： 王应前等人证明了每个既没有4圈又没有5圈的平面图是(1, 1, 0)-可染[5]的以及(3, 0, 0)-可染的[6]； 2017年， Cohen-Addad[7]等人已经列举出反例说明Steinberg猜想是错误的. 就对图的非正常染色的定义， 该领域已得到广泛的研究. 比如对相邻短圈的研究， 并得出许多有意义的结果： 王应前[8]等人证明了没有相邻5—圈的平面图是(1, 1, 0)-可染的； 李[9]等人证明了没有6圈和没有相邻4—_圈的平面图是(1, 1, 0)-可染的； Hoskins[10]等人证明了没有4圈和相邻三角形的平面图是(2, 0, 0)-可染的. 根据对以上问题的研究， 学者提出了如下一些问题.

问题设图G为一个不含相邻4—圈的平面图， 则

(1)图G是(1, 1, 0)-可染的；

(2)图G是(1, 0, 0)-可染的.

2 定理及其证明

定理1设图G是不含相交3圈， 且不含相邻4—圈的平面图， 那么G是(2, 2, 0)-可染的.

本文考虑的图都是有限的、 简单的、 无向的. 如果一个图形G可以嵌入到平面中, 使其边缘只在其两端相交， 则称图G为平面图. 分别用V,E,F表示图G的点集、 边集和面集， 图G记作图G=(V,E,F). 对任意的一个顶点v∈V,v的度数记作d(v). 称v分别为k-点，k--点和k+-点， 如果d(v)=k,d(v)≤k和d(v)≥k. 对任意点u,v∈V, 称uv∈E为图G的一条(d(u),d(v))-边，u称为v的 一个d(u)-邻点. 对任意的一个面f∈F,f的度数记作d(f). 称f分别为k-面、k--面和k+-面， 如果d(f)=k,d(f)≤k和d(f)≥k. 称f为一个(d(v1),d(v2), …,d(vk))-面， 如果f上的点v1,v2, …,vk是按某一时针方向连续出现的. 如果一个点或一条边与一个三角形相关联， 则称这个点或这条边是三角的. 称点v是d(u)-邻点m-面的， 如果v有一个邻点u, 且v和邻点u与一个m-面相关联. 称点v是k-三角的， 如果v关联k个三角形， 用fm(v)表示与v-点相关联的m-面的个数. 我们称点 为5b-点， 如果5-点v关联一个(3, 5, 6+)-面， 且另外三个点为3-点.

2.1 极小反例的结构性质

引理1δ(G)≥3.

证明反设v有两个邻点v1和v2. 由G的极小性，G-v有一个(2, 2, 0)-染色φ.v的两个邻点至多使用两种颜色染好， 此时v可用第三种颜色染好， 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理2G中非三角3点v至多只有一个4—-邻点.

证明反设v有两个4—-邻点v1和v2, 令v3为v的另一个邻点. 由G的极小性,G-v有一个(2, 2, 0)-染色φ. 可断言v的3个邻点必染不同的颜色， 否则v正常染好. 此时v1和v2中至少有一个点可染颜色1或颜色2. 由对称性, 不妨令φ(v1)=1, 则{1, 1, 2}∈φ(N(v1)v), 否则v直接染颜色1或者改染v1为2,v染1. 这时，v1改染颜色3, 再把v染1, 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理3设uv是一条(3, 3)-边， 且w是u,v的公共邻点， 则d(w)≥6.

证明反设d(w)≤5, 不妨设d(w)=5. 由G的极小性，G-u有一个(2, 2, 0)-染色φ. 可断言u的3 个邻点必染不同的颜色， 否则u正常染好. 令u′为u的另一个邻点， 若φ(u′)=3, 则u染与v相同的颜色. 故φ(u′)≠3, 由对称性， 不妨设φ(u′)=1. 如果φ(v)=2, 则u染颜色2； 故φ(v)=3, 则v的外邻点v′必染1, 否则v改染为1,u染3； 此时，φ(w)=2, 且{2, 2, 1}∈φ(N(w)v), 否则 直u接染颜色2或者改染w为1,u染颜色2. 此时w改染颜色3,v改染为颜色2,u染颜色2, 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理45-点v至多有4个3-邻点.

证明反设5-点v有5个5-邻点vi(i=1, 2, 3, 4, 5). 由G的极小性，G-{v,v1,v2, …,v5}有—个(2, 2, 0)-染色φ. 先按顺序依次正常染好vi(i=1, 2, 3, 4, 5). 如果

{1, 2, 3}∉φ(N(v)), 则v正常染好， 所以

{1, 2, 3}∈φ(N(v)). 可断言{1, 1, 2, 2, 3}∈φ(N(v)), 否则用没有出现的颜色去染v. 现在用1或2去染v, 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理5设5-点v关联一个(3, 5,d(u))-面， 且其他邻点为3-邻点， 则u为6+-点.

证明反设u为5--点， 不妨令d(u)=5. 令v的其他邻点分别为vi(i=1, 2, 3, 4)且d(v1)=d(v2)=d(v3)=d(v4)=3, 其中v4与u相邻， 且v4的外邻点为v41. 由G的极小性，G-{v,v1,v2,v3,v4}有一个(2, 2, 0)-染色φ. 先按顺序依次正常染好vi(i=1, 2, 3, 4).

显然{1, 2, 3}∈φ(N(v)), 否则v能够正常染好. 如果φ(u)=3, 则给v染{1, 2}两种颜色在N(v)中至多只出现两次. 故φ(u)≠3, 由对称性， 不妨令φ(u)=1. 此时分为两种情况.

1) 如果φ(v4)=3, 则

{2, 2, 2}∈φ(N(v){v4,u}), 否则v染2, 此时v41必染2, 否则v4改染为2,v染3;{1, 1, 2}∈φ(N(u)v4), 否则v直接染1或u改染为2, 再把v染1, 此时u改染为颜色3,v4改染为颜色1,v染颜色 1.

2) 当φ(v4)=2,{2, 2, 3}∈φ(N(u){v4,u}), 否则v染没有出现的那个颜色.φ(v41)=3, 否则v4改染为颜色 3,v染颜色2.

{1, 1, 3}∈φ(N(u)v4), 否则v直接染1或u改染为颜色3,v染1, 此时u改染为颜色2,v染1.

综上分析， 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理66-点v至多有5个3-邻点.

证明反设6-点v有6个3-邻点vi(i=1, 2, 3, 4, 5, 6). 由G的极小性，G-{v,v1,v2, …,v6}有一个(2, 2, 0)-染色φ. 先按顺序依次正常染好vi(i=1, 2, 3, 4, 5, 6). 可断言{1, 1, 1, 2, 2, 2}∈φ(N(v)), 否则用没有出现的那个颜色去染v. 此时， 用颜色3去染v, 则得到G的一个(2, 2, 0)-染色， 这与G的选取矛盾.

引理7设6-点v的邻点分别为vi(i=1, 2, 3, 4, 5, 6), 其中d(v1)=d(v2)=d(v3)=d(v4)=d(v5)=3, 且v5与v6相邻， 则v6不为5b-点.

证明反设v6为5b-点. 且v61,v62,v63是v6的 3个3-邻点， 则d(v61)=d(v62)=d(v63)=3.G的极小性，G-{v,v1,v2,v3,v4,v5,v6,v61,v62,v63}有一个(2, 2, 0)-染色φ. 先按顺序依次正常染好v1,v2,v3,v4,v61,v62,v63. 首先用{1, 2}颜色中至多只出现—次的颜色去染v6, 然后再正常染v5. 可断言{1, 1, 1, 2, 2, 2}∈φ(N(v)), 否则用没有出现的那个颜色去染v. 此时用颜色3去染v, 则得到G的一 个(2, 2, 0)-染色， 这与G的选取矛盾.

2.2 定理1的证明

假设定理1不成立. 设G=(V,E)是定理1关于顶点数最少的一个极小反例. 那就是说，G本身不是(2, 2, 0)-可染的， 但每个少于G的顶点数的子图都是(2, 2, 0)-可染的. 将G嵌入平面， 则得到平面图G=(V,E,F), 其中V为G的点集、E为G的边集、F为G的面集， 且具有上述所有结构性质. 我们首先假设G是2-连通的情况， 因此G的每一个面都是简单的. 接下来， 我们将规定权转移规则来推出矛盾， 进而证明定理1在2-连通时是成立的.

对连通平面图G， 由欧拉公式， 有

|V(G)|-|E(G)|+|F(G)|=2

对每一个x∈V(G)∪F(G)， 定义其初始权值为ch(x). 对任意v∈V(G)， 定义ch(v)=d(v)-6， 而对于f∈F(G)，ch(f)=2d(f)-6， 则

x∈V(G)∪F(G)， 都有ch′(x)≥0. 由于只在顶点和面之间进行权转移， 故权总和不变， 从而与

权转移规则如下：

(2) 设v为3-点， 且v1,v2,v3均为v的邻点， 设d(v2)，d(v3)=5+， 则

下面验证新权ch′(x)≥0，x∈V(G)∪F(G).

首先检验面的新权， 即

ch′(f)≥0，∀f∈F(G).

设d(f)=5+， 由(1)，知

设d(f)=4， 由(1)，知

设d(f)=3， 由权转移规则， 没有进行权转入和权转出， 所以ch′(f)=2d(f)-6=0.

接下来验证点的最终权满足

ch′(v)≥0，∀v∈V(G).

用fk(v)表示与v点相关联的k-面的个数. 因为G没有相交 -圈， 因此对任意v∈V(G)，f3(v)≤1.因为G中4—圈不相邻， 因此与4—圈相邻的面均是5+-面.

设d(v)=4. 由权转移规则， 4-点不向外转权. 若f3(v)=0， 则f4(v)≤2， 从而有

故f3(v)≠0. 令f3(v)=1， 则f4(v)≤1，

设d(v)=5.易知f4(v)≤2.由于5-点至多与 4 个 3-点相邻. 若f3(v)=0， 如果f4(v)=0， 由权转移规则(1)和(2)， 有

若f4(v)=1， 由权转移规则(2)，知

若f4(v)=1且v不为5b-点， 由权转移规则(2)，知

如果v不为5b-点， 显然，v至多与3个3-邻点， 则

综合以上各种情况， 得到如下矛盾的式子

上面的这个矛盾说明G不存在， 因此证明了定理1在G是2-连通时成立.

现在我们假设G不是2-连通的， 也就是说G有割点. 我们可以选取G的一个分块B， 令为G在B上的唯一割点， 令f0为B的外表面. 因为δ(G)≥3， 所以平面图B是2-连t*通的. 因此，B的每个面的边界都是一个圈，B的每个顶点v都与dB(v)个不同的面相关联. 显然，B既没有相交3-圈， 也没有相邻4—圈. 而且，G从引理2.1到引理2.7所建立的每一个性质只有在涉及到t*时不成立. 我们可以在B=(V(B),E(B),F(B))进行如下权转移规则.

初始权定义为： 对每一个x∈V(B)∪F(B)， 定义其初始权值为ch(x)=dB(v)-6.

由握手定理

和欧拉公式|V(G)|-|E(G)|+|F(G)|=2， 有

我们根据下列规则重新分配x∈V(B)∪F(B)的权ch(x).

r3. 对于x≠t*，f0, 我们按照G是2-连通的权转移规则(1)、 (2).

显然， 当B是2-连通时，

对x∈{V(B)∪F(B)}{t*,f0}能通过(1)、 (2)证明ch′(x)=dB(x)-6≥0. 对于t*和f0， 由r1和dB(t*)≥2， 有

由r2和dB(f0)≥3， 有

因此

从而证明了当G不是2-连通时定理1也成立. 因此， 定理1成立.