不含 3-圈平面图的线性染色＊

王 侃

(浙江师范大学数理与信息工程学院,浙江金华 321004)

0 引 言

本文所考虑的图都是简单图.用 V(G),E(G),Δ(G)和δ(G)分别表示图 G的顶点集、边集、最大度和最小度.G的围长 g(G)是指 G中最短圈的长度.

图 G的一个正常染色是从顶点集合 V(G)到颜色集合{1,2,…,k}的一个映射,使得任意 2个相邻的顶点染不同的颜色;图G的一个线性 k-染色是一个正常染色,使得染任意 2种颜色的顶点集合导出的子图是一些点不交的路的并;图 G的线性色数 lc(G)定义为 G的所有线性 k-染色中最小的 k值.

文献[1]首先研究了图的线性染色,证明了任意图 G的线性色数满足圈染色是 G的一个正常染色,使得染任意 2种颜色的顶点集合导出的子图是一个森林.无圈染色的概念是由 Grünbaum[2]提出的.这方面的研究可参阅文献[2-5].

2008年,Esperet等[6]把线性染色的概念推广到线性选择性,他们研究了树、格子图、完全二部图、平面图、外平面图、最大度为 3或 4的图以及有较小最大平均度的图的线性选择数.

定理 1[6]设 G是一个平面图,则

定理 2[7]设 G是一个平面图,则

1)若存在一个有序对 (Δ,g)∈{(13,7),(7,9),(5,11),(3,13)},使得Δ(G)≥Δ,g(G)≥g,那么

本文考虑围长至少为 4的平面图的线性染色,得到如下的结果:

定理 4 设M≥5是一个正整数,G是一个Δ(G)≤M且没有 3-圈的平面图,则

1 基本概念

对于一个平面图 G,用 F(G)表示它的面集合.对∀f∈F(G),若 u1,u2,…,un是 f边界上依序排列的顶点,则记 f=[u1u2…un],注意到点的重复出现是允许的.面的度是指它的边界上边的条数,其中割边被计算 2次.对∀x∈V(G)∪F(G),用 dG(x)表示 G中 x的度.在不产生混淆的情况下,可以用 d(x)代替 dG(x).一个度数为 k的顶点 (面)被称为 k-点 (k-面),一个度数至少为 k或至多为 k的顶点 (面)被称为 k+-点 (k+-面 )或 k--点 (k--面 ).用 NG(v)表示 G中 v的邻点的集合.

设 c是 G的一个部分线性染色,颜色集合为 C.对∀v∈V(G),用 C2(v)表示 C中正好在NG(v)上出现 2次的颜色子集合;对任意的顶点集合 T,用 C2＊(T)表示 C中至少在 T上出现 2次的颜色子集合.为了讨论方便,对 i=1,2,3,称恰关联 i个 4-面的 3-点为类型 i的,且称关联至多 1个 4-面的 3-点为好 3-点,关联至少 2个 4-面的 3-点为坏 3-点.

2 极小反例的性质

假设定理 4不成立.设 G是一个极小反例,即 G是一个没有 3-圈的平面图,满足Δ(G)≤M,且以下性质:

断言 1 δ(G)≥3.

证明 假设 G包含 1-点 v与某点 u相邻.显然,H=G-{v}是一个没有 3-圈的平面图,满足Δ(H)≤Δ(G).由 G的极小性知,H有一个线性染色 c应用颜色集合 C.为将 c扩充到整个图 G,用不在 C2(u)∪

假设 G包含一个 2-点 v,其邻点为 x,y.显然,H=G-{v}是一个没有 3-圈的平面图,满足Δ(H)≤Δ(G).由G的极小性知,H有一个线性染色c应用颜色集合C.用不在{c(x),c(y)}∪C＊2(NH(x)∪好 v.与 G的选择矛盾!断言 1证毕.

断言 2 G没有相邻 3-点.

证明 假设 G包含一条路 P=v1v2v3v4,使 d(vi)=3(i=2,3).ui-1是 vi的不同于 vi-1,vi+1(i=2,3)的邻点,如图 1所示.

显然,H=G-{v2}是一个没有 3-圈的平面图,满足Δ(H)≤Δ(G).由 G的极小性可得,H有一个线性染色 c应用颜色集合 C.若 c(u1),c(v1),c(v3)不全相同,则 v2的禁用颜色为{c(u1),c(v1),c(v3)}∪C＊2(NH(u1)∪NH(v1)∪NH(v3)).因|{c(u1),c(v1),c(v3)}|+5),故能用C中的颜色染v2.若c(u1)=c(v1)=c(v3),则用C({c(v1),c(v4),c(u2)}∪C＊2(NH(v4)∪NH(u2){v3}))中的颜色 a改染 v3.因 |{c(v1),c(v4),c(u2)}|+|C＊2(NH(v4)∪NH(u2){v3})|≤3+

图 1 断言 2中的子结构

断言 4 设 x1是和一个 4-面 f关联的 3-点,则 x1的 2个和 f关联的邻点一定是 5+-点.

证明 假设 G包含这样一个面 f=[x1x2x3x4],满足 d(x1)=3,d(x2)≤4.由断言 1和断言 2知,d(x2)=4.记 y1是 x1的不同于 x2和 x4的邻点;xj2(j=1,2)是 x2的不同于 x1和 x3的邻点,如图 2所示.

图 2 断言 4中的子结构

图 3 断言 5中的子结构

断言 5 不存在一个 5-点和 5个坏 3-点相邻.

证明 假设 G包含这样的一个 5-点 v,它的邻点 x1,x2,x3,x4,x5全是坏 3-点,则和 v关联的面中一定有 2个相邻 4-面,设为 f1=[vx1y1x2],f2=[vx5y2x1],如图 3所示.

显然,H=G-{x1}是一个没有 3-圈的平面图,满足Δ(H)≤Δ(G).由 G的极小性可得,H有一个线性染色 c应用颜色集合 C.考虑下面 2种情形染 x1:

1)c(y1),c(y2),c(v)不全相同.

用不在{c(y1),c(y2),c(v)}和C＊2(NH(y1)∪NH(y2)∪NH(v))中的颜色染x1,x1的禁用颜色数至

2)c(y1)=c(y2)=c(v).

用不在{c(y1),c(x2),c(x3),c(x4),c(x5)}和 C＊2(NH(x2)∪NH(x3)∪NH(x4)∪NH(x5){v,y1,(M≥5),所以可以用 C中的颜色染好 x1.断言 5证毕.

断言 6 不存在一个 5-点和至少 3个类型 3的 3-点相邻.

证明 假设 G包含这样一个 5-点 v,它的邻点中至少有 3个是类型 3的 3-点,则至少有 2个类型 3的 3-点是和 v关联于同一 4-面的.不失一般性,设 x1,x2,x3,x4,x5是 v的邻点,且 x1,x2都是类型 3的 3-点,x3,x4,x5中至少有 1个是类型 3的 3-点,则和 vx1,vx2关联的 3个面都是 4-面,设为 f1=[vx1y1x2],f2=[vx5y2x1],f3=[vx2y3x3],如图 4所示.

显然,H=G-{x1}是一个没有 3-圈的平面图,满足Δ(H)≤Δ(G).由 G的极小性可得,H有一个线性染色 c应用颜色集合 C.考虑用以下 2种情形染 x1:

1)c(y1),c(y2),c(v)不全相同.

3 定理 4的证明

设 G是定理 4的一个极小反例,为完成证明,应用权转移方法.首先,结合欧拉公式 |V(G)|-

定义初始权函数 w:对 v∈V(G),令 w(v)=d(v)-4;对 f∈F(G),令 w(f)=d(f)-4.由式 (1)得总的权和为 -8.然后定义一个权转移规则,且在所有的点和面上执行.一旦权转移结束,就会产生一个新的权函数 w′.

在整个权转移过程中权和是不变的,但对于所有的 x∈V(G)∪F(G),有 w′(x)≥0.这就导致了下面一个很明显的矛盾,因此这样的反例 G是不存在的:

权转移规则如下:

若 d(v)=4,则 w′(v)=w(v)=d(v)-4=0.

4 结 论

由定理 4立即推出下面结果:

[1]Yuster R.Linear coloring of graphs[J].DiscreteMath,1998,185(1/2/3):293-297.

[2]Grünbaum B.Acyclic colorings of planar graphs[J].Israel J Math,1973,14(4):390-408.

[3]Borodin O V.On acyclic colorings of planar graphs[J].DiscreteMath,1979,25(3):211-236.

[4]Kostochka A V.Acyclic 6-coloring of planar graphs[J].MetodyDiskretAnal,1976,28:40-56.

[5]Mitchem J.Every planar graph has an acyclic 8-coloring[J].DukeMath J,1974,41(1):177-181.

[6]EsperetL,MontassierM,Raspaud A.Linear choosability of graphs[J].DiscreteMath,2008,308(17):3938-3950.

[7]Raspaud A,WangW.Linear coloring of planar graphswith large girth[J].DiscreteMath,2009,309(18):5678-5686.

[8]Li Chao,WangWeifan,Raspaud A.Upper bounds on the linear chromatic number of a graph[J].DiscreteMath,2011,311(4):232-238.