1. 引言
本文中所考虑的图都是简单图,即没有环和重边。我们分别用
和G表示图G的点集和边集。两条边交叉指的是当图G嵌入到平面中时两条边相交不在端点处。当图G嵌入到平面中且每条边至多被相交一次,则我们称是图G的一个好的嵌入。我们用
表示图G的一个好的嵌入中的交叉次数。
对于一个图G,给图G的每一个顶点v指定一个颜色列表
。称j是G的一个L-点染色,是指对每一个点
,都存在一个颜色
,使得若
,则
。也称G是L-点可染的。若对任意指定的颜色列表L,使得对每一个
有
,G都存在一个L-点染色,则称G是k-列表点可染的,或称G是k-点可选的。G的列表色数或选择数定义为最小的整数k,使得G是k-点可选的,用
表示。图G的列表染色概念是1970年由Vizing [5] 提出,同时由Erdős,Rubin和Taylor [6] 独立提出。
定义1:设f是
到N上的一个映射。图G上的f列表染色游戏定义如下:
1) 该游戏有两位玩家Lister和Painter;
2) 起始时刻,G中的所有点都未染色且任意顶点v有
个筹码;
3) 在任意一个回合Lister选取图G中未染色顶点集的一个非空子集M,M中的每一个顶点减少一个筹码。Painter从M中选取一个独立集I,I中的顶点被染色;
4) 若某一个回合后,有一个未染色的顶点v没有筹码,则Lister赢得比赛。若某一回合后,所有顶点都染色了,则Painter赢得比赛。
定义2:对于图G上的f在线列表染色游戏,若Painter有一个赢得策略,则称G是在线f可选的。若对于
且G是在线f可选的,则称G是在线k可选的。G的在线列表色数或选择数定义为最小的整数k,使得G是在线k-可选的,用
表示。
在线列表染色概念是由U. Schauz [1] 和X. Zhu [2] 于2009年分别提出。由列表染色和在线列表染色定义,我们可得出
,即G的在线列表染色结果比G的列表染色结果要强。但是有时候他们是相等的,例如U. Schauz [1] 在文章中证明了平面图是在线5-可选的。对于在线列表染色,文献 [3] [4] [7] - [11] 等给出了一些结果。
2. 主要引理
为了证明平面图是在线5-可选的,Uwe Schauz [1] 证明了一下这个更强的结果:
引理1:令G是一个平面图,F是G的一个面并且
是F上的一条边。对于f是
到N的一个映射且使得:
·对于
,
,
·对于
,
,
·
和
,则
是在线f-可选的。
假设点v是G某的个子图H中的点且在第i步中被Lister选中,但这并不意味着Painter在选出相应独立集时I被选中。这是因为可能当我们在图H中考虑点v时,v被看作一个未被选中的点。这个情况发生是因为v有一个邻点u在另一个子图H中被Painter选中,这样我们说v因为u丢掉一个筹码。设
,
表示由S诱导出的子图。由引理1我们可得出一个重要的观察结论。
观察1:令G是一个图。f是
到N的一个映射。令
,并且对于任意
满足
。如果
是在线f-可选的并且
满足引理3.1的条件,那么G是在线f-可选的。
证明:假设在第i步,玩家Lister选出一个未染顶点集
。Painter需要从
中选出一个相应的独立集
,对于独立集
的选择需要一些步骤才能完成。Painter按照以下步骤先后考虑
中的点:
1) Painter从
中选出一个独立集
。
2) Painter从
中选出一个独立集
。
以上两步骤选出的独立集
,即Painter所对应选出的独立集
。接下来我们需要说明按照以上策略是玩家Painter在G的f-在线游戏中的一个赢得策略。我们说对于任意
,v有足够的筹码可用。这是因为如果
,那么因为
是在线f-可选的,从而Painter在
中有一个赢得策略,所以点v有足够的筹码可用。如果
,那么因为
都满足引理3.1的条件,从而Painter在图
中有一个赢得策略,所以点v有足够的筹码可用。因此以上策略是玩家Painter的一个赢得策略,G是在线f-可选的。
根据引理1和观察1,我们可以证出下面这个定理。
定理1:若图G满足
,那么G是在线5-选的。
证明:假设G满足
。令边
和
相互交叉。这样我们令
,以及
,并且
满足
。我们可以很容易验证出
是在线5-可选的,以及
满足引理1的条件。因此根据观察1,我们得出G是在线5-选的。
在研究含有交叉图的在线染色的过程中,我们发现了一个重要的定理。
定理2:令G是一个满足
的图,
为G中的一个三角形。若f是
到N的一个映射且使得对于
满足
,对于
满足
,那么
是在线f-可选的。
3. 极小反例的性质
假设定理3是不正确的和G是定理3的反例且满足:
1)
是最小的;
2) 在满足(1)的前提下,
是最大的。
假设G是一个连通图,因为否则我们可以考虑G的每一个连通分支且根据G的极小性,我们得出每一个连通分支是在线f-可选的,因此
是在线f-可选的。对于所有
有
。如果存在v有
,那么根据G的极小性
是在线f-可选的,由于
,所以
也是在线f-可选的。
引理2:
。
证明:假设
,则G是平面图。令
,我们容易得出
是在线f-可选的。令
以及
是
到N上的一个映射且满足。由于对于任意
在S中至多一个邻点,因此
满足引理的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
引理3:如果
是一条交又边,那么
。
证明:假设这个引理不正确,那么我们不妨设
并且被令一条边
交叉。根据对称性,我们假设
和x落在T的内部。令
是由T的外部以及T上的点所得到的G的一个诱导子图。根据G的极小性,我们有
是在线f-可选的。令
且
是在线f-可选的。令
以及
是
到N的一个映射且满足
。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
为了方便后面的证明,我们把交叉边和T都称作是坏的构型。
引理4:G没有分离3-圈。
证明:假设G存在一个分离三圈
且令
。
如果两个坏的构型都在G*内,那么根据G的极小性,我们有
是在线f-可选的。令
且
是在线f-可选的。令
以及
是
到N的一个映射满足
以及
,
。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
如果只有一个坏的构型在G*内,那么根据对称性我们假设T在G*内。根据G的极小性,我们有
是在线f-可选的。令
。根据G的极小性,我们有
是在线f-可选的,因为C在
中充当着T的角色。因此
是在线f-可选的。
引理5:设C是G的一个分离圈。如果坏的构型都在C的一侧,那么
。
证明:假设G中存在一个分离4-圈
。令
且坏的构型都在G*内。根据G的极小性,我们有
是在线f-可选的。令
,从而
是在线f-可选的。令
,以及
是
到N上的一个映射满足
且
,
。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
令
,且边
和
相互交叉。因为我们假设G的边数尽可能的多,所以我们可假设
是一个完全图。
引理6:令
。如果e是交又边,那么不存在
使得x与u和v相邻。
证明:假设存在点
使得w与u,v相邻。令X上按顺时针方向的点为
。那么
和
之间,由对称性我们假设坏的构型在
的一侧。根据引理5我们有
不是一个分离圈。这样我们得出
,从而产生矛盾。
引理7:如果C是G的一个分离4-圈,那么
。
证明:令C是G的一个分离4-圈并且
。根据引理5以及T和X之间的对称性,我们假设T在
内以及X在
内。根据G的极小性,我们有
是在线f-可选的。因为
是一个完全图,所以uv是G中的边。根据引理6,我们有uv不是交叉边并且
。根据引理4,从而C在
中是一个诱导子图。我们假设
,令
以及令
。以及
是
到N上的一个映射满足
且
,
。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
引理8:
。
证明:假设
。令
,以及
且uv不是交叉边。令
,很显然
是在线f-可选的。令
以及
是
到N上的一个映射且满足
且
,
。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
引理9:G中不存在边
使得
且
。
证明:假设
是G中的一条边。根据引理6以及
和
之间的对称性,我们假设
不是G中的边。令
。
情形1:G中不存在点w与
都相邻。
令
,且
是
到N上的一个映射且满足
并且
(
)。由于对于任意
在S中至多两个邻点,因此
满足引理1的条件。根据观察1,我们得出
是在线f-可选的,与G是极小反例相矛盾。
情形2:G中存在点点w与
都相邻。
根据引理6,我们有
不是G中的一条边,从而
。由于我们的假设
不是G中的边,所以
。根据引理7,对于
我们有
不是G中的边。根据引理4,我们有
不是G中的边,并且w是唯一的。令
,以及
是
到N上的一个映射且满足对于
都有
以及对于
有
。在第i回合玩家Lister选中一个未染顶点集
,玩家Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么玩家Painter按照顺序
选择在
中。
3) 如果
。玩家Painter一般优先考虑S中的点以及当
,Painter优先考虑w。当
时,此时我们需要考虑两种特殊情况:1)
,那么根据引理4,我们有
。如果
,Painter优先考虑
;2)
Painter优先考虑
。
由以上的策略,S中的点有足够的筹码可用,因此
是在线f-可选的。对于
中的点,我们需要说明
满足引理1的条件。由
定义可知
中的点除了w都有足够的筹码可用,因此我们只需要说明w在
中至少有3个筹码可用。根据以上的策略,点w最多因为
丢掉2个筹码,所以w在
中至少有3个筹码可用。从而
在线f-可选的,与G是反例相矛盾。
设P为G中的一条路且
,其中
和
并且P上的边都不是交叉边。
表示P的跨度。如果
,那么
;如果
,那么
。我们选择一条路P使得
最小。根据引理9,我们有令
,令
,根据P的选择我们得出
是G的一条诱导路。我们假设
。
引理10:如果
是
的邻点,那么
。
证明:如果
并且
,那么
的,这与P的选择相矛盾。
引理11:任意
在P上最多有三个邻点。
证明:假设存在
在P上有四个邻点。根据引理10以及P的选择,这四个邻点是
。由于
的跨度不小于P的跨度,所以
。我们有
或者
的G的一个分离圈,与引理4相矛盾。
根据P的选择,对于
,
在P上最多两个邻点并且这两个邻点是
。根据引理4,
最多与
中一个相邻。根据P的选择,
在P上有两个邻点。对于每个点
,如果v在P上有三个点,那么令
,其中
是v在P上下标最大的邻点;如果v在P上最多两个邻点,那么令
。
引理12:如果
,那么
。
证明:如果
且
,那么
在P上都有三个邻点。如果
,那么
,从而产生矛盾。因此
。由于P的选择,所以
邻点在
中。根据引理4,
不会都与
相邻。不失一般性我们假设
。因此u的邻点是
。根据引理7,我们得出
。这样
或者
是一个分离4-圈并且坏的构型在分离4-圈的一侧,与引理5相矛盾。
4. 定理2的证明
证明:令
。令
,以及
是
到N上的一个映射且满足对于
都有
除了那些在S上有三个邻点的点,以及对于
,
。
情形1:
。
1.1
中一个是G中的边。
我们假设
。在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么玩家Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。当y在P上的邻点是
,因为
以及根据引理4,我们有
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑
。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f -可选的,与G是反例相矛盾。
1.2
都不是G中的边。
在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么玩家Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
情形2:
。
A 不存在点
使得
。
A1
中一个是G中的边。
我们假设
。在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么玩家Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。当y在P上的邻点是
,因为
以及根据引理4,我们有
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑
。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f -可选的,与G是反例相矛盾。
A2
都不是G中的边。
在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么玩家Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
B 存在点
使得
。
B1 存在点
使得
。
B1.1
中一个是G中的边。
我们假设
。在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么Painter按照顺序
选择在
中,对于
,Painter优先考虑
。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。当y在P上的邻点是
,因为
以及根据引理4,我们有
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑
。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
B1.2
都不是G中的边。
在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么Painter按照顺序
选择在
中,对于
,Painter优先考虑
。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
B2 不存在点
使得
。
B2.1
中一个是G中的边。
我们假设
。在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。当y在P上的邻点是
,因为
以及根据引理4,我们有
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑
。当y在P上的邻点是
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑y。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点除了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
B2.2
都不是G中的边。
在第i回合Lister选中一个未染顶点集
,Painter按照以下策略选择
:
1) 对于
有
,玩家Painter优先选择
在
中。
2) 如果
,那么Painter按照顺序
选择在
中。
3) 如果
,玩家Painter一般优先考虑S中的点。当y在P上的邻点是
,其中
。如果
,那么Painter优先考虑
;如果
,那么玩家Painter优先考虑y。当y在P上的邻点是
。如果
,那么Painter优先考虑
;如果
,Painter优先考虑y。
由以上的策略,S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点
时,
会因为y丢失3个筹码,根据引理12,y是唯一的,所以
最多丢失4个筹码,
还有筹码可用。因此
是在线f-可选的。对于G中的点,我们需要说明
满足引理1的条件。由
定义可知G中的点了y都有足够的筹码可用,因此我们只需要说明
在
中至少有3个筹码可用。根据以上的策略,点y最多因为
丢掉2个筹码,所以y在
中至少有3个筹码。从而
在线f-可选的,与G是反例相矛盾。
致谢
感谢浙江师范大学“千人计划”朱绪鼎教授对本文的帮助,也感谢所有匿名审稿人对本文的指导意见。
基金项目
国家自然科学基金项目资助(CNSF 00571319)。