哈林图的弱点边染色

徐 闻, 陈 敏

(浙江师范大学 数学与计算机科学学院, 浙江金华321004)

§1 引 言

本文所研究的图均为有限无向简单图, 未定义的符号请参见文献[1]. 如果能将G画在平面上, 使得它的边仅在端点处相交, 则称G为可平面图. 一个平面图是指一个可平面图的平面嵌入.令V(G),E(G),F(G),∆(G)分别表示平面图G的点集, 边集, 面集以及最大度. 在平面上嵌入一棵树T, 使得T没有度为2的点, 且至少有一个度数不小于3 的顶点. 用圈C连接T的所有叶子点,这样得到的一个平面图叫做哈林图(Halin graph). 通常记为G=T ∪C, 其中T称为G的特征树.轮图是特殊的哈林图, 通常用Wn=K1+Cn−1表示n阶轮图, 其中Cn−1为n −1个顶点的圈.

平面图的点边染色(或称全染色)问题最早由Behzad[2]和Vizing[3]独立研究. 令G是一个图.图G是点边k-可染的是指存在映射π:V(G)∪E(G)→{1,··· ,k}, 使得任意两个相邻的顶点,任意两条相邻的边, 以及任意两个相关联的顶点和边都染不同的颜色. 图G的点边色数, 记为χve(G), 定义为使得G是点边k-可染的最小正整数k的值.

Behzad[2]猜想:每个简单图G都是点边(∆(G)+2)-可染的. Rosenfeld[4]和Vijayaditya[5]均证明了当∆(G) = 3时猜想成立. Kostochka[6]验证了∆(G)∈{4,5}的情形. 而Sanders和Zhao[7]证明了满足∆(G)≥7的平面图G是点边(∆(G)+2)-可染的. 进一步, Borodin[8]证明了∆(G)≥9的平面图G是点边(∆(G)+1)-可染的. 对于平面图的点边染色问题, ∆(G) = 6的情形至今仍未能完全解决.

近年来, 在点边染色的基础上, Fabrici, Jendrol’和Voigt[9]提出了一个新的染色概念, 即: 平面图的弱点边染色. 对于任意的两条相邻边e1和e2, 若它们关联同一个面且在该面的边界上连续出现, 则称e1和e2是面相邻的. 平面图G是弱点边k-可染的是指存在映射π:V(G)∪E(G)→{1,··· ,k}, 使得任意两个相邻的顶点, 任意两条面相邻的边, 以及任意两个相关联的顶点和边都染不同的颜色. 若平面图G有弱点边k-染色, 则称G是弱点边k-可染的. 平面图G的弱点边色数是指使得G是点边k-可染的最小正整数k的值, 用¯χve(G)表示. 显然, ¯χve(G)≤χve(G). 在文献[10]中, Fabrici, Jendrol’和Vrbjarov´a证明了每个无环且无割边的连通平面图是弱点边6-可染的. 此外, 极大平面图和外平面图也均由Fabrici, Jendrol’和Voigt[10]证明是弱点边5-可染的.

本文旨在找出其他满足弱点边5-可染的平面图类, 得到以下结论.

定理1 哈林图是弱点边5-可染的.

需指出存在轮图W4的弱点边色数恰好为5, 详见引理1. 由此可见定理1的上界5是可达的.

§2 引理与记号

令G是哈林图. 设v ∈V(G), 用dG(v)表示v在G中的度数, 用NG(v)表示v在G中的邻点全体.称V(C)构成的无界面为外面,记为fo,其余面为内面. 称V(fo)中的顶点为外点,V(G)−V(fo)中的顶点为内点. 记G的全体内点的集合为Vint(G), 显然Vint(G) =V(G)V(fo). 称与外点相邻的内点为半叶子点. 进一步, 如果一个半叶子点仅和一个内点相邻, 则称其为好半叶子点.

引理1 对于轮图Wn, 有¯χve(Wn)≤5. 特别地, ¯χve(W4)=5, 而且当n为奇数时, 有

证记轮图Wn的内点为v0, 其余外点按顺时针方向依次为v1,v2,··· ,vn−1. 根据n的奇偶性分两种情况讨论.

情形1 当n=2k+1, 其中k ≥2.

For small angular spread,exploiting the spatial frequency approximation model,the covariance matrix R can be approximated and expressed as

由于v1为3-点, 易知v1v0,v1v2,v1vn−1以及v1这四个元素的颜色各不相同, 因此

§3 定理1的证明

图1 结构(A1)和结构(A2)

情形1G包含结构(A1).

令G∗=G −{v1,v2}+{xv,yv}. 显然G∗是哈林图, 满足∆(G∗)=∆(G), 且

根据归纳假设,G∗有一个弱点边5-染色π∗.

不妨设π∗(v) = 1,π∗(vu) = 2,π∗(xv) = 3, 以及π∗(vy) = 4. 将xv,vy的颜色赋给G中的元素xv1和yv2. 记A={xv1,yv2}与S={v1,v2,vv1,vv2,v1v2}. 然后, 令π(s) =π∗(s), 其中s ∈V(G)∪E(G)(A ∪S). 接下来说明S中的元素可以正常染好, 从而说明π∗可以被延拓至G, 使得G有一个弱点边5-染色π.

不难看出π(y)∈{2,3,5}. 下面按照π(y)的值分两种子情况展开讨论.

情形1.1:π(y)=3.

可给v2染颜色5, 给vv2染颜色3, 给vv1染颜色5, 给v1v2染1. 然后给v1染一种属于

的颜色. 不难验证所得的染色是G的一个弱点边5-染色.

情形1.2:π(y)∈{2,5}.

可给v2染颜色3,vv2染颜色5,vv1染颜色4,v1v2染颜色1. 然后给v1染一种属于

的颜色. 容易验证得到的染色是G的一个弱点边5-染色.

情形2G包含结构(A2).

令G∗=G −{v1,v2,··· ,vt}+{xv,yv}. 显然G∗是哈林图, 满足∆(G∗)=∆(G), 且

根据归纳假设G∗有一个弱点边5-染色π∗. 同样将证明π∗可以被延拓至G.

首先令

其次将xv,yv在G∗中的颜色分别赋予对应于G中的元素xv1和yvt. 记A={xv1,yvt}及

然后令π(s) =π∗(s), 其中s ∈V(G)∪E(G)(A ∪S). 接下来根据t的奇偶性分情况说明S中的元素也可被染好.

情形2.1:t为偶数.

首先给vv1染颜色3, 给vvt染颜色2. 对于2≤i ≤t −1, 若i为奇数, 则给边vvi−1染颜色2, 给边vvi染颜色3, 给边vi−1vi染颜色5, 给边vivi+1染颜色1. 进而给点vi−1染颜色3,vi染颜色2. 然后给边v1v2染颜色1. 最后给v1染颜色α ∈{4,5}{π(x)}, 给vt染颜色β ∈{4,5}{π(y)}. 此时得到的染色是G的一个弱点边5-染色.

情形2.2:t为奇数.

首先给vv1染颜色3, 给vvt染颜色2. 对于2≤i ≤t −2, 若i为奇数, 则给边vvi−1染颜色2,给边vvi染颜色3, 给边vi−1vi染颜色5, 给边vivi+1染颜色1. 然后, 给点vi−1染颜色3,vi染颜色2,vt−1染颜色3, 给边v1v2染颜色1. 之后, 给v1染颜色α ∈{4,5}{π(x)}, 给vt染颜色

最后给vvt−1染颜色β, 给边vt−1vt染颜色γ ∈{4,5}{β}即可. 容易验证G是弱点边5-可染的.

§3 结语