稀疏图的(3,4)-染色

胡黎莉

（闽南师范大学数学与统计学院,福建漳州 363000）

仅考虑有限简单图.沿用文献[1]的记号，除非另有说明.

若图G的顶点集可以分为V1和V2两部分，使得在G的导出子图G[V1]和G[V2]中，顶点的最大度分别是d1和d2，则称G是(d1,d2)-可染色的.令g(G)表示图G的围长并令.Βorodin等[2]证明了mad(G)＜7/3的图G是(1,0)-可染的.Choi等[3]证明了围长大于等于5的平面图是(3,5)-可染的.Choi 等[4]证明了围长大于等于5 的平面图是(3,4)-可染的.Βorodin 等[5]证明了围长大于等于5 的平面图是(2,6)-可染的.

证明了以下结果.

定理1若图G满足mad(G)＜19/6，则G是(3,4)-可染的.

由于平面图G满足,故由定理1可得以下推论.

推论1围长大于等于6的平面图是(3,4)-可染的.

1 预备知识和引理

称度为d(≥d,≤d)的顶点为d-度点(d+-点,d--点).设v∈V(G)，若v有一个邻点u的度为d，则称u是v的d-邻点.对于5 ≤k≤7,如果一个k-度点和k-1个2-度点相邻，则称它是坏-点.轻-点是2-度点或坏点.

设G是定理的一个反例，使得|V(G)|最小.显然，G连通且δ(G)≥2.令i∈{3,4}且c是G或G的子图的一个染色.若c(v)=i且v有i个邻点染颜色i，则称v是i-饱和的.根据定义，一个i-饱和点至少有i个邻点.用颜色3和4给G的某个子图染色，使得染颜色i的所有顶点的导出子图的最大度至多是i(i∈{3,4}).

引理1若d(v)=2,则v和两个5+-点相邻,且其中一个是6+-点.

证明设N(v)={v1,v2}.由G的极小性知G-v有一个(3,4)-染色c.若c(v1)=c(v2),则v可正常染色,矛盾.不失一般性，假设c(v1)=3且c(v2)=4.由于令c(v)=3不能得到G的一个(3,4)-染色，故v1是3-饱和点；由于令c(v1)=4和c(v)=3不能得到G的一个(3,4)-染色，故v1有一个4-饱和邻点.因此，d(v1)≥5.同理可证，d(v2)≥6.

引理2若d(v)=3,则v至少和两个5+-点相邻,且其中一个是6+-点.

证明设N(v)={u,v3,v4}.由G的极小性知G-v有一个(3,4)-染色c.若c(u)=c(v3)=c(v4),则v可正常染色,矛盾.不失一般性，假设c(v3)=3且c(v4)=4.进一步假设c(u)=i，其中i∈{3,4}且j∈{{3,4} {i}}.

由于令c(v)=j不能得到G的一个(3,4)-染色，故vj是j-饱和的；由于令c(vj)=i和c(v)=j不能得到G的一个(3,4)-染色，故vj有一个邻点染颜色i.从而，d(vj)≥j+2.由于令c(v)=i不能得到G的一个(3,4)-染色,故u或vi是i-饱和点.若d(u)≤i+1 且d(vi)≤i+1,则给{u,vi}中的i-饱和点重新染颜色j并令c(v)=i，得到G的一个(3,4)-染色，矛盾.因此，u和vi至少有一个是(i+2)+-点.

引理3若d(v)≤8,则v至少和一个5+-点相邻.

证明用反证法.假设v的邻点都是4--点.由G的极小性知G-v有一个(3,4)-染色c.显然颜色3和4都必须出现在N(v)的染色中,否则v可正常染色,矛盾.由于v的邻点都是4--点，故v不能和4-饱和点相邻；由于令c(v)=4不能得到G的一个(3,4)-染色，故v至少有5个邻点染颜色4；由于令c(v)=3不能得到G的一个(3,4)-染色且d(v)≤8，故v有一个3-饱和邻点.又因为v的邻点都是4--点，可以重新给v的3-饱和邻点分配颜色4再给v染颜色3，由此得到G的一个(3,4)-染色，矛盾.

引理4G中的每个5--点至少和一个6+-点相邻.

证明用反证法.假设v是G中的一个5--点，它的邻点都是4--点.由G的极小性知，G-v有一个(3,4)-染色.显然颜色3 和4 均出现在N(v)的颜色中,否则v可正常染色,矛盾.给v染颜色4.这种染色方式会出现的唯一一个问题是存在v的邻点，记作u，它染颜色4 且有5 个邻点染颜色4.由于d(u)≤5，可以重新给u染颜色3.对于v的这类邻点我们都重复这一过程，最终得到G的一个(3,4)-染色，矛盾.

引理5G中的6-度点不能和6个轻-点相邻.

证明用反证法.假设v是G中的一个6-度点，它的邻点都是轻-点.由G的极小性知，G-v有一个(3,4)-染色.若v存在2-邻点，则先对v的2-邻点重新正常染色.如果v至多有4 个邻点染颜色4，则给v染颜色4.这种染色方式会出现的唯一一个问题是存在v的邻点，记作u，它染颜色4 且有5 个邻点染颜色4.由于d(u)≤7，可以重新给u染颜色3.因此，假设v至少有5个邻点染颜色4并给v染颜色3.这种染色方式会出现的唯一一个问题是存在v的坏邻点，记作w，它染颜色3且有4个邻点染颜色3.由于d(w)≤7，可以重新给w染颜色4，最终得到G的一个(3,4)-染色，矛盾.

引理6G中的两个坏-点不能相邻.

证明用反证法.假设u和v是G中的两个坏-点且uv∈E(G).在G中删去u,v及它们的邻点，所得的图记为G′.由G的极小性知G′有一个(3,4)-染色.先给u和v的2-邻点正常染色.由于d(u)≤7，存在i∈{3,4}，使得u至多有3个邻点染颜色i.给u染颜色i.类似地，可以给v染颜色j∈{3,4}，由此得到G的一个(3,4)-染色，矛盾.

引理7假设d(v)=5且v有3个2-邻点，则：

1)如果v有一个3-邻点，则v不能和坏的6-度点相邻.

2)v不能和两个坏的6-度点相邻.

证明1)用反证法.假设v有一个3-邻点和一个坏的6-邻点，记作u.在G中删去u和v，所得的图记为G′.由G的极小性知G′有一个(3,4)-染色.先给u和v的2-邻点重新正常染色.由于d(u)=6，存在i∈{3,4}，使得u至多有2个邻点染颜色i.给u染颜色i.如果v的所有邻点都染相同的颜色，则v可正常染色，矛盾.因此，假设颜色3和4均出现在N(v)的颜色中.可以给v染颜色4,由此得到G的一个(3,4)-染色，矛盾.

2)否则，假设v有两个坏的6-邻点，记作u1和u2.由G的极小性知，G-v有一个(3,4)-染色.先对v的2-邻点重新正常染色.由于d(v)=5，存在i∈{3,4}，使得v至多有2 个邻点染颜色i.给v染颜色i.这种染色方式会出现的唯一一个问题是u1（或u2）染颜色i且有i+1个邻点染颜色i.由于d(u1)=6(d(u2)=6)，可以给u1（或u2）重新分配颜色{3,4}{i}.易见G中染颜色3（或4）的顶点的导出子图的最大度依旧不超过3（或4），于是得到G的一个(3,4)-染色，矛盾.

引理8假设d(v)=6且v有4个2-邻点，则：

1)v不能和两个坏的5-度点相邻.

2)如果v和一个坏的5-度点相邻，则v不能和3-度点或坏的6-度点相邻.

证明1)否则，假设v有两个坏的5-邻点，记作u1和u2.由G的极小性知，G-v有一个(3,4)-染色.先对v的2-邻点重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3 个邻点染颜色i.给v染颜色i.这种染色方式会出现的唯一一个问题是u1（或u2）染颜色i且有i+1 个邻点染颜色i.由于d(u1)=5(d(u2)=5)，我们可以给u1（或u2）重新分配颜色{3,4}{i}，进而得到G的一个(3,4)-染色，矛盾.

2)记v的坏5-邻点为u.用反证法.首先假设v和一个3-度点相邻.由G的极小性知，G-v有一个(3,4)-染色.先对v的2-邻点重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3个邻点染颜色i.给v染颜色i.这种染色方式会出现的唯一一个问题是u染颜色i且有i+1个邻点染颜色i.由于d(u)=5，可以给u重新分配颜色{3,4}{i}，进而得到G的一个(3,4)-染色，矛盾.

假设v和一个坏的6-度点w相邻.由G的极小性知，G-v有一个(3,4)-染色.先对v的2-邻点重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3 个邻点染颜色i.给v染颜色i.这种染色方式会出现的唯一一个问题是u（或w）染颜色i且有i+1 个邻点染颜色i.由于d(u)=5(d(w)=6)，可以给u（或w）重新分配颜色{3,4}{i}，进而得到G的一个(3,4)-染色，矛盾.

引理9假设d(v)=7且v有5个2-邻点，则v不能和两个坏的5-度点相邻.

证明用反证法.假设v有两个坏的5-邻点，记作u1和u2.由G的极小性知，G-v有一个(3,4)-染色.先对v的2-邻点重新正常染色.由于d(v)=7，存在i∈{3,4}，使得v至多有3个邻点染颜色i.给v染颜色i.这种染色方式会出现的唯一一个问题是u1（或u2）染颜色i且有i+1 个邻点染颜色i.由于d(u1)=5(d(u2)=5)，可以给u1（或u2）重新分配颜色{3,4}{i}，进而得到G的一个(3,4)-染色，矛盾.

2 定理1的证明

下面将采用权转移方法导出矛盾，从而完成定理的证明.对于任意的v∈V(G)，假设v的初始权值为w(v)=6d(v)-19.由mad(G)＜19/6可得.然后根据权转移规则，重新分配顶点的权，v的最终权记为w′(v).

权转移规则如下：

R1.G的每个5+-点向其每个2-邻点转移权值7/2.

R2.G的每个4+-点向其每个3-邻点转移权值1/2.

R3.G的每个6+-点向其每个相邻的坏5-度点转移权值3.

R4.G的每个5+-点向其每个相邻的坏6-度点转移权值1/2.

为了方便起见，记v的2-邻点的个数为t.下面分7种情况讨论：

1)若d(v)≥8,则根据R1～R4，w′(v)≥6d(v)-19-7/2d(v)=5/2d(v)-19 ≥1.

2)假设d(v)=7.首先假设v是坏点，则t=6 且由引理3 和引理6 知，v和一个5+-点相邻且该点不是坏点.由R1 得，w′(v)≥6×7-19-6×7/2=2.设v不是坏点，则t≤5.若t≤4,则由R1～R4，w′(v)≥6×7-19-4×7/2-3×3=0.若t=5，则由引理9 可知，v至多和一个坏的5-度点相邻.从而，根据R1～R4，w′(v)≥6×7-19-5×7/2-3-1/2=2.

3)假设d(v)=6.首先假设v是坏点，则t=5 且由引理3 和引理6 知，v和一个5+-点相邻且该点不是坏点.根据R1 和R4，w′(v)≥6×6-19-5×7/2+1/2=0.假设v不是坏点，则t≤4.令t=4.若v不与坏的5-度点相邻，则w′(v)≥6×6-19-4×7/2-2×1/2=2.若v有坏的5-邻点，则由引理8 知，这样的邻点只有一个且v不能和3-度点或坏的6-度点相邻.从而，由R1和R3得，w′(v)≥6×6-19-4×7/2-3=0.当t≤3时，由引理5可知,v至少有一个邻点不是轻-点.从而，当1 ≤t≤3 时，由R1～R4 可得w′(v)≥6×6-19-3×7/2-2×3-1/2=0；当t=0时，由R2～R4可得w′(v)≥6×6-19-3×5-1/2=3/2.

4)假设d(v)=5.首先假设v是坏点，则t=4 且由引理4 和引理6 知，v和一个6+-点相邻且该点不是坏点.根据R1 和R3，w′(v)≥6×5-19-4×7/2+3=0.现假设v不是坏点，则t≤3.若t≤2,则由R1,R2 和R4 可得，w′(v)≥6×5-19-2×7/2-3×1/2=5/2.假设t=3.若v既没有3-邻点也没有坏的6-邻点，则根据R1～R4,w′(v)≥6×5-19-3×7/2=1/2.假设v有一个3-邻点,则由引理7(1)，v不能和坏的6-度点相邻.因此，根据R1,R2 和R4,w′(v)≥6×5-19-3×7/2-1/2=0.若v有一个坏的6-邻点,则根据引理7 知，v的最后一个邻点不是坏的6-度点也不是3-度点.从而，根据R1,R2 和R4,w′(v)≥6×5-19-3×7/2-1/2=0.

5)若d(v)=4,则根据R2，w′(v)≥6×4-19-4×1/2=3.

6)若d(v)=3,则由引理2知，v至少和两个5+-点相邻.从而，根据R2,w′(v)≥6×3-19+2×1/2=0.

7)若d(v)=2,则由引理1知，v至少和两个5+-点相邻.从而，根据R1,w′(v)≥6×2-19+2×7/2=0.