1. 引言
在这篇文章中我们只考虑无向有限简单图。平面图是指能够嵌入到平面内的图。设G为一个平面图,其点集、边集和面集分别记为
、
和
。一个面f的规模是它的边界上的顶点数,记为
。
定义为这个图G中最小面的规模:
。图G的顶点的k-染色是一种映射
。如果任意两个相邻的点染不同颜色则称
为正常染色。如果所有k种颜色都出现在一个面
上,则称这个面为多色的。如果一个顶点的k-染色
使得G的每个面都是多色的,则称
为图G的一个多色k-染色。G的多色染色数p(G)是使得G存在多色k-染色时最大的k。对于任意的平面图G,定义:
很显然对任意的平面图G都有
。1969年Lovász [1] 证明了每个简单平面图G都有
。1999年Mohar和Škrekovski [2] 使用四色定理对Lovász的结果给出了另一种证明。2009年Alon等人 [3] 给出了对于一般平面图的多色染色数的上下界。
定理1.1 [3]
,
,当
时,
从定理1.1可以看出,当
时
的取值范围是2个或者3个整数。
平面图的多色染色在组合学和计算几何中有着很多应用,以下是1975年Chvátal [4] 提出并且证明的艺术画廊定理。
定理1.2 [4] 设P是一个有n个顶点的多边形,则
个顶点足够用来保护P。
定理1.2说明在P中存在一个含有
个点的点集S,使得S中的点可以监测到整个多边形P的面,此时称为S保护P,S称为保护集。保护问题与多色染色问题有着密切联系。对于平面图G,寻找最小的点集S使得G的每个面都与S中至少一个点关联。其实G的多色染色中每种颜色对应的点集是一个保护集,因为每种颜色都会出现在所有面上,每种颜色对应的点共同保护了G。
2012年Horev等人 [5] 研究了最大度3的二部图的多色4-染色问题并证明了以下定理:
定理1.3 [5] 最大度3的二部图是正常多色4-可染的。
如果存在一个平面嵌入使得图中所有顶点都属于外平面,则这样的平面图称为外平面图。在外平面图中最小面的规模等于最小圈的长度(围长)。以下定理表明了对于
的外平面图多色染色数的非平凡上界
是紧的。
定理1.4 [3] 设G是一个外平面图且满足
,则G存在一种使用g种颜色的多色正常染色。
通过上面的结果我们可以看到对于一些类别的图可以将多色染色数
提高到g,而通过定理1.1可知
的范围由g唯一决定,现在我们考虑一类平面图,在这类图中可以将多色染色数的下界
提高。
考虑一类含有较多二度点的平面图,这些二度点在两个面的共同边界上,这些点染上的颜色会同时出现在两个面上。若能在一个平面图G的每个面的边界上收缩w个二度点,则在所得平面图
中最小面的规模减小为
,根据定理1.1可知此时
。再将之前每个面上收缩的w个二度点恢复,并且将这些点染w种不同颜色,这样每个面都增加了种新颜色,从而
。当
时这个下界严格高于
,部分改进了定理1.1
的下界。
2. 简化对偶图的构造
定义2.1 设G是含有较多二度点的平面图,我们定义简化对偶图
:
1) 定义点集
,即G的每个面对应H的每个点;
2) 定义边集E(H) = {uv |面u与面v有公共的边界路},即这两个面的公共边界上有二度点。特别地,如果两个平面的公共边界上有多条边界路,在简化对偶图中对应两点也只有一条边。显然H的边对应的是原图中两个面公共的边界路;
3) 设e为H中的边,定义边的权重w(e)为e连接的两个点对应的面上公共的二度点数。
这样定义的简化对偶图H也是简单平面图。
若H的边集E(H)的子集
满足
,即
中的边可以包含H的所有点,则称
为H的一个边覆盖。
3. 主要结果
定理3.1 假设G是一个平面图,最小面的规模为g,H = H(G)是它的简化对偶图。如果H是一个偶圈,则E(H)可以分解成两个不相交的匹配
和
,并且
,
。
证明 设
,则H有2个不相交的匹配
和
。令
,
。在
中每条边对应公共边界路上去掉任意
个2-点,再在
中每条边对应公共边界路上去掉任意
个2-点,得到平面图
,
。根据定理1.1,可给出
的
种颜色的多色染色
,再将
恢复为G,基于染色
得到G的部分染色
。注意到G的每个面上恰有
个2-点未染色,现在用不同于
中的
个新颜色去染每个面上的未染色点,则每个面上可以出现这
个新颜色。显然有
定义3.2 设v是H中的点且
,v在原图中对应的面规模为g(v),定义点权
。
定理3.3 假设G是一个平面图,最小面的规模为g,
是它的简化对偶图。如果H是一个奇圈,
,则
有2k + 1个不同的最小边覆盖
(
),并且
其中
。
证明 设
,则
有2k + 1个不同的最小边覆盖
(
)。对任意
,点
对应的H的最小边覆盖记为
(下标模2k + 1),令
。对每个
都可进行下列操作:在图G中对
中每条边对应的公共边界路上去掉任意
个2-点,得到平面图
。面v在
中的规模记为
,对于任意的
,
。对于面
:由
,有
,
所以G中规模最小的面在
中仍然规模最小,所以
。由定理1.1可给出
的
种颜色的多色染色
。将
恢复为G,基于
染色得到G的部分染色
。注意到G中除
以外的面上恰有
个2-点未染色,(
对应面上有
个2-点未染色),现在用不同于
中的
种新颜色去染每个面上的未染色点,则每个面上可以出现这
种新颜色,容易看出
对应面上这
种新颜色各出现2次。显然
。对所有
,令
,显然有
。
定理3.4 假设G是一个平面图,最小面的规模为g,
是它的简化对偶图。如果H是一个星,
是星的中心点,令
,则
。
证明 设
,存在唯一的边覆盖
,星中心点
满足
。在
中每条边对应的公共边界路上去掉任意
个2-点,得到平面图
。面v在
中的规模记为
,对于任意的
,
。对于面
:
由
,
,所以G中规模最小的面在
中仍然规模最小,所以
。由定理1.1可给出
的
种颜色的多色染色
。将
恢复为G,基于
染色得到G的部分染色
。注意到G中除
以外的面上恰有
个2-点未染色,(
对应面上有
个2-点未染色),现在用不同于
中的
种新颜色去染每个面上的未染色点,则每个面上可以出现这
种新颜色,容易看出
对应面上这
种新颜色各出现n次。显然
。
致谢
在论文完成之际我要特别感谢我的导师张霞副教授。本文是在张霞副教授的悉心指导和严格要求下完成的,她对文章的每个章节和字词都仔细检查和指导,付出了自己的大量时间,她严肃的科研态度、严谨的治学精神、精益求精的工作作风一直激励着我,督促我不断改进自身不足和探索进取。在此我向我的导师致以深深的谢意。最后我向各位尊敬的评审专家致以最诚挚的感谢,谢谢你们对本论文做出的评审以及提出的宝贵意见。