Operations Research and Fuzziology
Vol.08 No.02(2018), Article ID:24444,9
pages
10.12677/ORF.2018.82006
Online List Colouring of Graphs with Crossing Number
Jianzhang Hu
Department of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 28th, 2018; accepted: Apr. 13th, 2018; published: Apr. 20th, 2018
ABSTRACT
The concept of online list colouring was introduced in 2009 by U. Schauz [1] and independently by X. Zhu [2] . Since the concept of online list colouring is put forward, many scholars have studied the online list colouring of the related graphs. For example, U. Schauz [1] has proved that each planar graph is online 5-paintable; M. Han and X. Zhu [3] have proved that locally planar graphs are 5-paintable; M. Han and X. Zhu [4] have proved that every planar graph is 1-defective (9,2)-paintable, etc. In this paper we prove that G is 5-paintable with crossing number at most one.
Keywords:List Colouring, Online List Colouring, Crossings Number, Independent Set
含有交叉数的图的在线列表染色
胡建章
浙江师范大学数理与信息工程学院,浙江 金华
收稿日期:2018年3月28日;录用日期:2018年4月13日;发布日期:2018年4月20日
摘 要
在线列表染色概念是由U. Schauz [1] 和X. Zhu [2] 于2009年分别提出。在线列表染色概念提出以来,不少学者研究了相关图的在线列表染色。例如,U. Schauz [1] 证明了平面图是在线5-可选的,M. Han和X. Zhu [3] 证明了局部平面图是在线5-可选的,M. Han和X. Zhu [4] 证明了每个平面图是1-缺陷在线(9,2)可选的,等相关性成果。在本文中我们证明了含有至多一个交叉的图是在线5-可选的。
关键词 :列表染色,在线列表染色,交叉数,独立集
Copyright © 2018 by author and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
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)。
文章引用
胡建章. 含有交叉数的图的在线列表染色
Online List Colouring of Graphs with Crossing Number[J]. 运筹与模糊学, 2018, 08(02): 45-53. https://doi.org/10.12677/ORF.2018.82006
参考文献
- 1. Schauz, U. (2009) Mr. Paint and Mrs. Correct. Electronic Journal of Combinatorics, 16, 18.
- 2. Zhu, X. (2009) On-Line List Colouring of Graphs. Electronic Journal of Combinatorics, 16, 3665-3677.
- 3. Han, M. and Zhu, X.D. (2015) Locally Planar Graphs Are 5-Paintable. Discrete Mathematics, 338, 1740-1749. https://doi.org/10.1016/j.disc.2014.11.015
- 4. Han, M. and Zhu, X. (2016) Every Planar Graph Is 1-Defective (9,2)-Paintable. arXiv:1605.04415 [math.CO]
- 5. Vizing, V.G. (1976) Coloring the Vertices of a Graph in Prescribed Colors. Diskret. Analiz., No. 29. (In Russian)
- 6. Erdős, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Congressus Numerantium, 26, 125-157.
- 7. Chang, T. and Zhu, X. (2012) On-Line 3-Choosable Planar Graphs. Taiwanese Journal of Mathematics, 16, 511-519. https://doi.org/10.11650/twjm/1500406598
- 8. Han, M. and Zhu, X. (2016) Locally Planar Graphs Are 2-Defective 4-Paintable. European Journal of Combinatorics, 54, 35-50. https://doi.org/10.1016/j.ejc.2015.12.004
- 9. Wong, T. and Zhu, X. (2013) Partial Online List Coloring of Graphs. Journal of Graph Theory, 74, 359-367. https://doi.org/10.1002/jgt.21714
- 10. Kim, S., Kwon, Y.S., Liu, D.D., et al. (2012) On-Line List Colouring of Complete Multipartite Graphs. Electronic Journal of Combinatorics, 19.
- 11. Lason, M. and Lubawski, W. (2017) On-Line List Coloring of Matroids. Discrete Applied Mathematics, 217, 353-355. https://doi.org/10.1016/j.dam.2016.08.002