1. 引言
图的染色是图论研究领域中相当活跃的一部分,也是非常重要的研究课题,其研究的问题来源于著名的四色猜想。如今,图的经典染色这一概念已经向很多方面进行推广和延伸,平面图的列表染色问题便是其中之一。1976年,Vizing [1] 提出了图的列表染色的概念,1979年由Erdős [2] 等人推广了列表染色定义,后被广泛研究。
令N表示正整数集合。设图G的一个映射
。G的f-列表配置是给图G的点集合的列表配置L,每个点v有一个颜色集合
,集合
有
个颜色。对于G的列表配置L,我们说G是L-可染的如果存在G的一个真染色f使得对于任意一个顶点v,都有
。图G的染色数用
表示,是指最小的正整数k使得图G是k-可染的。如果对于G的任意一个f-列表配置L,图G是L可染的,则称图G是f-可选的。如果图G是f-可选的,当f是一个常数函数即
时,我们就说G是k-可选。图G的选择数用
表示,是指最小的正整数k使得图G是k-可选的。
关于平面图的可选性问题,1979年Erdős [2] 等人全面分析了2-可选图。1994年,Thomassen [3] 证明了每一个平面图都是5-可选的。对于一个给定的图能否判断出是3-可选或4-可选的还未解决。1996年,Gutner [4] 证明了这些问题是NP-困难的。
Schauz [5] 于2009年在图的列表染色基础上,介绍了一种新型动态列表染色方法——图的在线列表染色。定义如下。
定义1:设图G的一个映射
。图G上的f列表染色游戏定义如下:该游戏有两位玩家:Lister和Painter。起初,图G中所有点均未被染色,且任意顶点v有
个筹码。在任意一个回合,Lister选择图G中未染色顶点集的一个非空子集M,M中每一个顶点减少一个筹码。Painter选择M中一个独立集I且I中的顶点被染色。若某一回合后,存在一个点v未被染色且没有筹码了,则Lister赢得比赛。若某一回合后,所有点均被染色了,则Painter赢得比赛。
定义2:设映射
。如果Painter在图G上的f列表染色游戏中有一个赢的策略,我们称图G是在线f可选的。如果图G是在线f可选的且常数函数
(k是常数),则称图G是在线k-可选的。图G的在线选择数用
表示,是指最小的正整数k使得G是在线k-可选的。
由列表染色的定义和在线列表染色的定义易知,若平面图G是在线f-可选的,则图G是f-可选的,因此有
。在另一方面,
这一差值也可以任意大。
关于平面图的在线可选性问题,2012年,Chang和Zhu [6] 证明了若G是不含3圈的平面图,且没有4圈与4圈或4圈与5圈相邻,则图是G在线3-可选的。2015年,Han和Zhu [7] 证明了局部平面图是在线5-可选的。
本文,我们研究的图均为有限,简单(无环,无重边)图。设G是一个平面图,
是图G的顶点集,
是图G的边集,
表示边集的大小。
表示顶点x在图中G的度。令
和
分别图G的最大度和最小度,
表示图G的最大出度。对于
,我们令
表示由S诱导的子图。图G是d-退化的若图G的每一个子图H有一个顶点的度在图H中至多为d。易知每一个d-退化的图是
-可选的。
2. 不含3, 5或6圈的平面图
使用欧拉公式可知,不含3圈的平面图是3-退化的。2002年Wang和Lih [8] [9] 证明了不含5圈的平面图是3-退化的。同年,Juvan和Mohar [9] 证明了不含6圈的平面图是3-退化的。于是我们有了下面的定理3。
定理3: [8] [9] 令k是一个整数,其中
或6。若平面图G不含k圈,则图G是3-退化的。
下面我们将给出本节要证的主要结论,即下述定理4。
定理4:令k是一个整数,其中
或6。若平面图G不含k圈,则图G是在线4-可选的。
为证明定理4,需要下述几个引理的支持。引理5是证明在线列表染色问题中一个非常有用的命题, [10] 中的推论8是比引理5更强的结论且已被证明。这里我们重新说明一下引理5的证明,后面我们将利用引理5证明引理6。
引理5:设A是一个集合,其中
。若
是在线f可选的,则图G是在线f-可选的。
证明:因为
是在线f-可选的,所以Painter在
上有一个赢的策略。
首先,Lister选择
的任意一个顶点子集X,然后Painter按照赢的策略先将
中的顶点染好颜色。接下来Painter染
中的顶点。对于
中的顶点,Painter需要一个一个的查看,查看
中的顶点有没有邻点被染色的。若
中的顶点的邻点未被染色,则将该点染色;若
中的顶点的邻点被染色,则该顶点不染色且失去一个筹码。也就是说,若存在某个顶点u,
,顶点u的筹码数减少1,但顶点u未被染色,则说明u的邻点被染色了。当u的邻点都已染好时,因为
,所以在剩余的图中,顶点u的筹码数总是大于0的,即游戏这样进行下去,
中的点都会被染色。所以Painter在图G有一个赢的策略,即图G是在线f-可选的。 □
引理6:若平面图G是3-退化的,则图G是在线4-可选的。
证明:对图G的点数作归纳法。设v是图G中一个度数小于等于3的顶点,即
,由归纳法假设可知,
是3-退化的,则
是在线4-可选的。设集合
,因此由引理5可知,图G是在线4-可选的。 □
由定理3和引理6易知,定理4成立。
3. 不含4圈的平面图
Lam,Xu和Liu在 [11] 证明了不含4圈的平面图是4-可选的,即下述定理7。
定理7: [11] 不含4圈的平面图是4-可选的。
[11] 中令
表示一个特殊的不含4圈的平面图,即
是由一个5面和一个外部相邻三角形组成的。令H是图G的一个子图,若H同构于
且对于任意
都有
,则H叫做
-子图。
引理8: [11] 设图G是不含4面且不含相邻三角形的平面图。若
,则图G包含一个
-子图。
易知,若一个图不含4圈,则该图不含4面且不含有相邻三角形。本节我们主要证明下述定理9。
定理9:若平面图G不含4圈,则图G是在线4-可选的。
显然定理9是定理7的在线版本,是比定理7更强的结论。对于定理9的证明,我们采用Alon和Tarsi [12] 的方法,找到图G的一个好的定向。在证明主要结论之前,我们先给出一些已知定义及结论,以便我们的证明。
3.1. 已有结论简介
假设D是图G的定向图,用
表示在D中已定向的边或弧的集合。若
,则x是y的入邻点且y是x的出邻点。顶点v的出度
和入度
分别是顶点v在定向图D中出邻点的个数和入邻点的个数。
设
是D的一个子图,若对于D中的每一个顶点v,有
,则
是一个欧拉子图。若
是奇数,则
是奇的欧拉子图;若
是偶数,则
是偶的欧拉子图。令
表示D的偶的欧拉子图的集合,
表示D的奇的欧拉子图的集合。设
(1)
若
,则我们称D是图G的一个好的定向图。
Alon和Tarsi [12] 的下述结论是研究列表染色的一个强有力的工具,称为Alon-Tarsi定理。
Alon-Tarsi定理 [12] 若D是图G的一个好的定向图,且对任意顶点v都有
,则图G是f-可选的。
Schauz [5] 将Alon-Tarsi定理延拓至在线列表染色的研究,即下述定理10。
定理10: [5] 若D是图G的一个好的定向图,且对任意顶点v都有
,则图G是在线f-可选的。
3.2. 证明定理12
下面我们将给出强的定向图的定义,显然定义11是比好的定向图更强的定义。
定义11:设X是
的一个子集。
是
的一个定向图,如果下列条件成立:
1)
,
2) 对于每一个顶点
,有
;
我们称
是
的一个强的定向图。
如果
有一个强的定向图,我们称子图
是可约的。
定理12:若图G是不含4圈的平面图,则图G有一个
的好的定向图D。
本文通过证明定理12的成立来说明定理9是成立的。采用反证法,首先假设定理12是错误的,且图G是关于最小度的极小反例。我们建立一些极小反例的性质。
引理13:图G不含可约结构。
证明:假设
是
的一个强的定向图,那么
。由图G的极小性可知,
有一个
的好的定向图
,那么
。令D是G的定向图,其中D是
与
的并,定向图D是把X和
之间的所有边定向为从X指向
。因为X和
之间所有边均是从X指向
的,所以D的任何欧拉子图都不含有从X指向
的边。那么
综上,我们可知
。因为对于每个顶点
,都有
,因此
。这与图G是极小反例是矛盾的。□
Figure 1. The orientation of
图1.
的定向图
下面我们给出定理12的证明过程。
证明:假设图G是关于最小度的极小反例,则
。因为图G不含4圈,所以G不含4面且不含相邻三角形。由引理8可知,G有一个
-子图H,其中
且
。令
是图G的筹码数,对于每一个点
,有
。由图G的极小性可知,
是在线4-可选的。令
表示点
可用的筹码数,则对于
,有
,对于
,有
。假设当
,
;当
,
。如图1所示,构造
的一个强的定向图
,易知对于每一个顶点
,有
且
,即
是可约结构,这与引理13矛盾。 □
上述我们完成了定理12的证明,也就证明了定理9是成立的,即不含4圈的平面图是在线4-可选的。结合第二节我们可以得到下述定理14。
定理14:当
或6时,不含k圈的平面图是在线4-可选的。
致谢
感谢浙江师范大学朱绪鼎教授对本文的建议,也感谢所有匿名审稿人对本文的指导意见。
基金项目
国家自然科学基金项目资助(CNSF 00571319)。