含有交叉数的图的在线列表染色 Online List Colouring of Graphs with Crossing Number

doi:10.12677/ORF.2018.82006

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

●How to Cite this Article

Department of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua Zhejiang

Received: Mar. 28^th, 2018; accepted: Apr. 13^th, 2018; published: Apr. 20^th, 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-可选的。

关键词 :列表染色，在线列表染色，交叉数，独立集

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文中所考虑的图都是简单图，即没有环和重边。我们分别用 $V (G)$ 和G表示图G的点集和边集。两条边交叉指的是当图G嵌入到平面中时两条边相交不在端点处。当图G嵌入到平面中且每条边至多被相交一次，则我们称是图G的一个好的嵌入。我们用 $c r (G)$ 表示图G的一个好的嵌入中的交叉次数。

对于一个图G，给图G的每一个顶点v指定一个颜色列表 $L (v)$ 。称j是G的一个L-点染色，是指对每一个点 $v \in V (G)$ ，都存在一个颜色 $φ (v) \in L (v)$ ，使得若 $x y \in E (G)$ ，则 $φ (x) \neq φ (y)$ 。也称G是L-点可染的。若对任意指定的颜色列表L，使得对每一个 $v \in V (G)$ 有 $| L (v) | \geq k$ ，G都存在一个L-点染色，则称G是k-列表点可染的，或称G是k-点可选的。G的列表色数或选择数定义为最小的整数k，使得G是k-点可选的，用 $χ_{l} (G)$ 表示。图G的列表染色概念是1970年由Vizing [5] 提出，同时由Erdős，Rubin和Taylor [6] 独立提出。

定义1：设f是 $V (G)$ 到N上的一个映射。图G上的f列表染色游戏定义如下：

1) 该游戏有两位玩家Lister和Painter；

2) 起始时刻，G中的所有点都未染色且任意顶点v有 $f (v)$ 个筹码；

3) 在任意一个回合Lister选取图G中未染色顶点集的一个非空子集M，M中的每一个顶点减少一个筹码。Painter从M中选取一个独立集I，I中的顶点被染色；

4) 若某一个回合后，有一个未染色的顶点v没有筹码，则Lister赢得比赛。若某一回合后，所有顶点都染色了，则Painter赢得比赛。

定义2：对于图G上的f在线列表染色游戏，若Painter有一个赢得策略，则称G是在线f可选的。若对于 $f (v) \equiv k$ 且G是在线f可选的，则称G是在线k可选的。G的在线列表色数或选择数定义为最小的整数k，使得G是在线k-可选的，用 $χ_{p} (G)$ 表示。

在线列表染色概念是由U. Schauz [1] 和X. Zhu [2] 于2009年分别提出。由列表染色和在线列表染色定义，我们可得出 $χ_{l} (G) \leq χ_{p} (G)$ ，即G的在线列表染色结果比G的列表染色结果要强。但是有时候他们是相等的，例如U. Schauz [1] 在文章中证明了平面图是在线5-可选的。对于在线列表染色，文献 [3] [4] [7] - [11] 等给出了一些结果。

2. 主要引理

为了证明平面图是在线5-可选的，Uwe Schauz [1] 证明了一下这个更强的结果：

引理1：令G是一个平面图，F是G的一个面并且 $e = x y$ 是F上的一条边。对于f是 $V (G)$ 到N的一个映射且使得：

·对于 $v \in V (G) - V (F)$ ， $f (v) \geq 5$ ，

·对于 $v \in V (F) - {x, y}$ ， $f (v) \geq 3$ ，

· $f (x) = 1$ 和 $f (y) = 1$ ，则 $G - e$ 是在线f-可选的。

假设点v是G某的个子图H中的点且在第i步中被Lister选中，但这并不意味着Painter在选出相应独立集时I被选中。这是因为可能当我们在图H中考虑点v时，v被看作一个未被选中的点。这个情况发生是因为v有一个邻点u在另一个子图H中被Painter选中，这样我们说v因为u丢掉一个筹码。设 $S \subseteq V (G)$ ， $G [S]$ 表示由S诱导出的子图。由引理1我们可得出一个重要的观察结论。

观察1：令G是一个图。f是 $V (G)$ 到N的一个映射。令 $G^{'} = G - S$ ，并且对于任意 $v \in V (G^{'})$ 满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 。如果 $G [S]$ 是在线f-可选的并且 $(G^{'}, f^{'})$ 满足引理3.1的条件，那么G是在线f-可选的。

证明：假设在第i步，玩家Lister选出一个未染顶点集 $L_{i}$ 。Painter需要从 $L_{i}$ 中选出一个相应的独立集 $I_{i}$ ，对于独立集 $I_{i}$ 的选择需要一些步骤才能完成。Painter按照以下步骤先后考虑 $L_{i}$ 中的点：

1) Painter从 $V (S) \cap L_{i}$ 中选出一个独立集 $I_{S}$ 。

2) Painter从 $V (G^{'}) \cap (L_{i} - I_{S})$ 中选出一个独立集 $I_{G^{'}}$ 。

以上两步骤选出的独立集 $I_{S} \cup I_{G^{'}}$ ，即Painter所对应选出的独立集 $I_{i}$ 。接下来我们需要说明按照以上策略是玩家Painter在G的f-在线游戏中的一个赢得策略。我们说对于任意 $v \in V (G)$ ，v有足够的筹码可用。这是因为如果 $v \in S$ ，那么因为 $G [S]$ 是在线f-可选的，从而Painter在 $G [S]$ 中有一个赢得策略，所以点v有足够的筹码可用。如果 $v \in V (G^{'})$ ，那么因为 $(G^{'}, f^{'})$ 都满足引理3.1的条件，从而Painter在图 $G^{'}$ 中有一个赢得策略，所以点v有足够的筹码可用。因此以上策略是玩家Painter的一个赢得策略，G是在线f-可选的。

根据引理1和观察1，我们可以证出下面这个定理。

定理1：若图G满足 $c r (G) = 1$ ，那么G是在线5-选的。

证明：假设G满足 $c r (G) = 1$ 。令边 $e = x x^{'}$ 和 $e^{'} = y y^{'}$ 相互交叉。这样我们令 $S = {x, y}$ ，以及 $G^{'} = G - S$ ，并且 $f^{'} : V (G^{'}) \to N$ 满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 。我们可以很容易验证出 $G [S]$ 是在线5-可选的，以及 $(G^{'}, f^{'})$ 满足引理1的条件。因此根据观察1，我们得出G是在线5-选的。

在研究含有交叉图的在线染色的过程中，我们发现了一个重要的定理。

定理2：令G是一个满足 $c r (G) \leq 1$ 的图， $T = t_{1} t_{2} t_{3}$ 为G中的一个三角形。若f是 $V (G)$ 到N的一个映射且使得对于 $v \in V (T)$ 满足 $f (v) = 1$ ，对于 $v \in V (G) - V (T)$ 满足 $f (v) = 5$ ，那么 $G - E (T)$ 是在线f-可选的。

3. 极小反例的性质

假设定理3是不正确的和G是定理3的反例且满足：

1) $| V (G) |$ 是最小的；

2) 在满足(1)的前提下， $| E (G) |$ 是最大的。

假设G是一个连通图，因为否则我们可以考虑G的每一个连通分支且根据G的极小性，我们得出每一个连通分支是在线f-可选的，因此 $G - E (T)$ 是在线f-可选的。对于所有 $v \in V (G) - V (T)$ 有 $d_{G} (v) \geq 5$ 。如果存在v有 $d_{G} (v) = 4$ ，那么根据G的极小性 $(G - {v}) - E (T)$ 是在线f-可选的，由于 $f (v) > d (v)$ ，所以 $G - E (T)$ 也是在线f-可选的。

引理2： $c r (G) = 1$ 。

证明：假设 $c r (G) = 0$ ，则G是平面图。令 $S = t_{1}$ ，我们容易得出 $G [S]$ 是在线f-可选的。令 $G^{'} = G - S$ 以及 $f^{'}$ 是 $V (G^{'})$ 到N上的一个映射且满足。由于对于任意 $v \in V (G^{'})$ 在S中至多一个邻点，因此 $(G^{'}, f^{'})$ 满足引理的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

引理3：如果 $e = x y$ 是一条交又边，那么 $e \notin E (T)$ 。

证明：假设这个引理不正确，那么我们不妨设 $e = t_{1} t_{2}$ 并且被令一条边 $e^{'} = x^{'} y^{'}$ 交叉。根据对称性，我们假设 $x \neq t_{3}$ 和x落在T的内部。令 $G_{1}$ 是由T的外部以及T上的点所得到的G的一个诱导子图。根据G的极小性，我们有 $G_{1} - E (T)$ 是在线f-可选的。令 $S = V (G_{1}) - {t_{2}, t_{3}}$ 且 $G [S]$ 是在线f-可选的。令 $G^{'} = G - S$ 以及 $f^{'}$ 是 $V (G^{'})$ 到N的一个映射且满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 。由于对于任意 $v \in V (G^{'})$ 在S中至多两个邻点，因此 $(G^{'}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

为了方便后面的证明，我们把交叉边和T都称作是坏的构型。

引理4：G没有分离3-圈。

证明：假设G存在一个分离三圈 $C = x y z$ 且令 $G^{*} = int [C]$ 。

如果两个坏的构型都在G^*内，那么根据G的极小性，我们有 $G^{*} - E (T)$ 是在线f-可选的。令 $S = G^{*} - {x, y}$ 且 $G [S]$ 是在线f-可选的。令 $G^{'} = G - S$ 以及 $f^{'}$ 是 $V (G)$ 到N的一个映射满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 以及 $f^{'} (x) = 1$ ， $f^{'} (y) = 1$ 。由于对于任意 $v \in V (G^{'})$ 在S中至多两个邻点，因此 $(G^{'}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

如果只有一个坏的构型在G^*内，那么根据对称性我们假设T在G^*内。根据G的极小性，我们有 $G^{*} - E (T)$ 是在线f-可选的。令 $G^{'} = G - int [C]$ 。根据G的极小性，我们有 $G^{'} - E (C)$ 是在线f-可选的，因为C在 $G^{'}$ 中充当着T的角色。因此 $G - E (T)$ 是在线f-可选的。

引理5：设C是G的一个分离圈。如果坏的构型都在C的一侧，那么 $l (C) \geq 5$ 。

证明：假设G中存在一个分离4-圈 $C = v_{1} v_{2} v_{3} v_{4}$ 。令 $G^{*} = int [C]$ 且坏的构型都在G^*内。根据G的极小性，我们有 $G^{*} - E (T)$ 是在线f-可选的。令 $S = V (G^{*}) - {v_{1}, v_{2}}$ ，从而 $G [S]$ 是在线f-可选的。令 $G^{'} = G - S$ ，以及 $f^{'}$ 是 $V (G^{'})$ 到N上的一个映射满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 且 $f^{'} (v_{1}) = 1$ ， $f^{'} (v_{2}) = 1$ 。由于对于任意 $v \in V (G^{'})$ 在S中至多两个邻点，因此 $(G^{'}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

令 $X = {x_{1}, x_{2}, x_{3}, x_{4}}$ ，且边 $e = x_{1} x_{3}$ 和 $e^{'} = x_{2} x_{4}$ 相互交叉。因为我们假设G的边数尽可能的多，所以我们可假设 $G [X]$ 是一个完全图。

引理6：令 $e = u v \in E (G [X])$ 。如果e是交又边，那么不存在 $x \in G - X$ 使得x与u和v相邻。

证明：假设存在点 $w \in G - X$ 使得w与u，v相邻。令X上按顺时针方向的点为 $x, u, y, v$ 。那么 $x u w v$ 和 $y u w v$ 之间，由对称性我们假设坏的构型在 $y u w v$ 的一侧。根据引理5我们有 $y u w v$ 不是一个分离圈。这样我们得出 $d_{G} (y) \leq 4$ ，从而产生矛盾。

引理7：如果C是G的一个分离4-圈，那么 $| V (C) \cap X | \leq 1$ 。

证明：令C是G的一个分离4-圈并且 $V (C) \cap X = {u, v}$ 。根据引理5以及T和X之间的对称性，我们假设T在 $G^{'} = int [C]$ 内以及X在 $G^{″} = e x t [C]$ 内。根据G的极小性，我们有 $G^{'} - E (T)$ 是在线f-可选的。因为 $G [X]$ 是一个完全图，所以uv是G中的边。根据引理6，我们有uv不是交叉边并且 $u v \in E (C)$ 。根据引理4，从而C在 $G^{″}$ 中是一个诱导子图。我们假设 $C = u v x y$ ，令 $V (G^{'}) - {x, y}$ 以及令 $G_{1} = G - S$ 。以及 $f^{'}$ 是 $V (G_{1})$ 到N上的一个映射满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 且 $f^{'} (x) = 1$ ， $f^{'} (y) = 1$ 。由于对于任意 $v \in V (G_{1})$ 在S中至多两个邻点，因此 $(G_{1}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

引理8： $X \cap T = \emptyset$ 。

证明：假设 $X \cap T = {u}$ 。令 $T = u t_{2} t_{3}$ ，以及 $u v \in E (G [X])$ 且uv不是交叉边。令 $S = {u, v}$ ，很显然 $G [S]$ 是在线f-可选的。令 $G^{'} = G - S$ 以及 $f^{'}$ 是 $V (G)$ 到N上的一个映射且满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 且 $f^{'} (t_{2}) = 1$ ， $f^{'} (t_{3}) = 1$ 。由于对于任意 $v \in V (G^{'})$ 在S中至多两个邻点，因此 $(G^{'}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

引理9：G中不存在边 $e = u v$ 使得 $u \in T$ 且 $v \in X$ 。

证明：假设 $t_{1} x_{1}$ 是G中的一条边。根据引理6以及 $x_{2}$ 和 $x_{4}$ 之间的对称性，我们假设 $t_{1} x_{4}$ 不是G中的边。令 $S = {t_{1}, x_{1}, x_{2}}$ 。

情形1：G中不存在点w与 $t_{1}, x_{1}, x_{2}$ 都相邻。

令 $G^{'} = G - S$ ，且 $f^{'}$ 是 $V (G^{'})$ 到N上的一个映射且满足 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 并且 $f^{'} (t_{i}) = 1$ ( $i = 2, 3$ )。由于对于任意 $v \in V (G^{'})$ 在S中至多两个邻点，因此 $(G^{'}, f^{'})$ 满足引理1的条件。根据观察1，我们得出 $G - E (T)$ 是在线f-可选的，与G是极小反例相矛盾。

情形2：G中存在点点w与 $t_{1}, x_{1}, x_{2}$ 都相邻。

根据引理6，我们有 $t_{1} x_{3}$ 不是G中的一条边，从而 $w \neq t_{3}$ 。由于我们的假设 $t_{1} x_{4}$ 不是G中的边，所以 $w \neq x_{4}$ 。根据引理7，对于 $i = 2, 3$ 我们有 $x_{2} t_{i}$ 不是G中的边。根据引理4，我们有 $t_{3} x_{1}$ 不是G中的边，并且w是唯一的。令 $G^{'} = G - S$ ，以及 $f^{'}$ 是 $V (G^{'})$ 到N上的一个映射且满足对于 $v \in V (G^{'}) - {w}$ 都有 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 以及对于 $i = 2, 3$ 有 $f^{'} (t_{i}) = 1$ 。在第i回合玩家Lister选中一个未染顶点集 $L_{i}$ ，玩家Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么玩家Painter按照顺序 $t_{1}, x_{1}, x_{2}$ 选择在 $I_{i}$ 中。

3) 如果 $L_{i} ⊄ S$ 。玩家Painter一般优先考虑S中的点以及当 $x_{2}, w \in L_{i}$ ，Painter优先考虑w。当 $x_{1}, w \in L_{i}$ 时，此时我们需要考虑两种特殊情况：1) $t_{2} x_{1} \in E (G)$ ，那么根据引理4，我们有 $t_{2} w \notin E (G)$ 。如果 $t_{2}, x_{1}, w \in L_{i}$ ，Painter优先考虑 $t_{2}, w$ ；2) $t_{2} x_{1} \notin E (G)$ Painter优先考虑 $x_{1}$ 。

由以上的策略，S中的点有足够的筹码可用，因此 $G [S]$ 是在线f-可选的。对于 $G^{'}$ 中的点，我们需要说明 $(G^{'}, f^{'})$ 满足引理1的条件。由 $f^{'}$ 定义可知 $G^{'}$ 中的点除了w都有足够的筹码可用，因此我们只需要说明w在 $G^{'}$ 中至少有3个筹码可用。根据以上的策略，点w最多因为 $t_{1}, x_{1}$ 丢掉2个筹码，所以w在 $G^{'}$ 中至少有3个筹码可用。从而 $G - E (T)$ 在线f-可选的，与G是反例相矛盾。

设P为G中的一条路且 $P = p_{1} p_{2} \dots p_{k - 1} p_{k}$ ，其中 $p_{1} \in T$ 和 $p_{k - 1}, p_{k} \in X$ 并且P上的边都不是交叉边。 $W (P)$ 表示P的跨度。如果 $p_{k - 2} p_{k} \in E (G)$ ，那么 $W (P) = 2 k - 1$ ；如果 $p_{k - 2} p_{k} \notin E (G)$ ，那么 $W (P) = 2 k$ 。我们选择一条路P使得 $W (P)$ 最小。根据引理9，我们有令 $k \geq 4$ ，令 $\bar{P} = p_{1} p_{2} \dots p_{k - 1}$ ，根据P的选择我们得出 $\bar{P}$ 是G的一条诱导路。我们假设 $p_{1} = t_{1}$ 。

引理10：如果 $p_{i}, p_{j}$ 是 $v \in V (G) - V (P)$ 的邻点，那么 $| i - j | \leq 2$ 。

证明：如果 $| i - j | \geq 3$ 并且 $i > j$ ，那么 $W (\bar{P}) < W (P)$ 的，这与P的选择相矛盾。

引理11：任意 $v \in V (G) - V (P)$ 在P上最多有三个邻点。

证明：假设存在 $v \in V (G) - V (P)$ 在P上有四个邻点。根据引理10以及P的选择，这四个邻点是 $p_{k - 3}, p_{k - 2}, p_{k - 1}, p_{k}$ 。由于 $p_{1} p_{2} \dots p_{k - 3} v p_{k} p_{k - 1}$ 的跨度不小于P的跨度，所以 $p_{k - 2} p_{k} \in E (G)$ 。我们有 $p_{k - 2} p_{k} v$ 或者 $p_{k - 2} p_{k - 1} v$ 的G的一个分离圈，与引理4相矛盾。

根据P的选择，对于 $i = 2, 3$ ， $t_{i}$ 在P上最多两个邻点并且这两个邻点是 $t_{1}, p_{2}$ 。根据引理4， $p_{2}$ 最多与 $t_{2}, t_{3}$ 中一个相邻。根据P的选择， $v \in X - {p_{k - 1}, p_{k}}$ 在P上有两个邻点。对于每个点 $V (G) - V (P)$ ，如果v在P上有三个点，那么令 $σ (v) = p_{i}$ ，其中 $p_{i}$ 是v在P上下标最大的邻点；如果v在P上最多两个邻点，那么令 $σ (v) = v$ 。

引理12：如果 $u \neq v$ ，那么 $σ (u) \neq σ (v)$ 。

证明：如果 $u \neq v$ 且 $σ (u) = σ (v) = p_{i}$ ，那么 $u, v$ 在P上都有三个邻点。如果 $p_{i} \neq p_{k}$ ，那么 $d_{G} (p_{i - 1}) \leq 4$ ，从而产生矛盾。因此 $p_{i} = p_{k}$ 。由于P的选择，所以 $u, v$ 邻点在 ${p_{k - 3}, p_{k - 2}, p_{k - 1}, p_{k}}$ 中。根据引理4， $u, v$ 不会都与 $p_{k - 1}$ 相邻。不失一般性我们假设 $u p_{k - 1} \notin E (G)$ 。因此u的邻点是 $p_{k - 3}, p_{k - 2}, p_{k}$ 。根据引理7，我们得出 $v p_{k - 1} \notin E (G)$ 。这样 $p_{k - 2} p_{k - 1} p_{k} u$ 或者 $p_{k - 2} p_{k - 1} p_{k} v$ 是一个分离4-圈并且坏的构型在分离4-圈的一侧，与引理5相矛盾。

4. 定理2的证明

证明：令 $S = V (P)$ 。令 $G^{'} = G - S$ ，以及 $f^{'}$ 是 $V (G^{'})$ 到N上的一个映射且满足对于 $v \in V (G^{'})$ 都有 $f^{'} (v) = f (v) - | N_{G} (v) \cap S |$ 除了那些在S上有三个邻点的点，以及对于 $i = 2, 3$ ， $f^{'} (t_{i}) = 1$ 。

情形1： $p_{k - 2} p_{k} \notin E (G)$ 。

1.1 $t_{2} p_{2}, t_{3} p_{2}$ 中一个是G中的边。

我们假设 $t_{2} p_{2} \in E (G)$ 。在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么玩家Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

3) 如果 $L_{i} ⊄ S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_{i}, p_{i + 1}, p_{i + 2}$ ，其中 $2 \leq i \leq k - 2$ 。如果 $p_{i}, p_{i + 1}, y \in L_{i}$ ，那么Painter优先考虑 $p_{i}, p_{i + 1}$ ；如果 $p_{i + 2}, y \in L_{i}$ ，那么玩家Painter优先考虑y。当y在P上的邻点是 $p_{1}, p_{2}, p_{3}$ ，因为 $t_{2} p_{2} \in E (G)$ 以及根据引理4，我们有 $t_{2} y \notin E (G)$ 。如果 $t_{2}, p_{2}, y \in L_{i}$ ，那么Painter优先考虑 $t_{2}, y$ ；如果 $p_{2}, y \in L_{i}$ ，Painter优先考虑 $p_{2}$ 。

由以上的策略，S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点 $p_{i}, p_{i + 1}, p_{i + 2}$ 时， $p_{i + 2}$ 会因为y丢失3个筹码，根据引理12，y是唯一的，所以 $p_{i + 2}$ 最多丢失4个筹码， $p_{i + 2}$ 还有筹码可用。因此 $G [S]$ 是在线f-可选的。对于G中的点，我们需要说明 $(G^{'}, f^{'})$ 满足引理1的条件。由 $f^{'}$ 定义可知G中的点除了y都有足够的筹码可用，因此我们只需要说明 $f^{'}$ 在 $G^{'}$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_{i}, p_{i + 1}$ 丢掉2个筹码，所以y在 $G^{'}$ 中至少有3个筹码。从而 $G - E (T)$ 在线f -可选的，与G是反例相矛盾。

1.2 $t_{2} p_{2}, t_{3} p_{2}$ 都不是G中的边。

在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么玩家Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

情形2： $p_{k - 2} p_{k} \in E (G)$ 。

A 不存在点 $v \in V (G) - V (P)$ 使得 $σ (v) = p_{k}$ 。

A1 $t_{2} p_{2}, t_{3} p_{2}$ 中一个是G中的边。

我们假设 $t_{2} p_{2} \in E (G)$ 。在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么玩家Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

A2 $t_{2} p_{2}, t_{3} p_{2}$ 都不是G中的边。

在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么玩家Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

B 存在点 $v \in V (G) - V (P)$ 使得 $σ (v) = p_{k}$ 。

B1 存在点 $w \in V (G) - V (P)$ 使得 $σ (w) = p_{k - 2}$ 。

B1.1 $t_{2} p_{2}, t_{3} p_{2}$ 中一个是G中的边。

我们假设 $t_{2} p_{2} \in E (G)$ 。在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}$ 选择在 $I_{i}$ 中，对于 $p_{k - 1}, p_{k}$ ，Painter优先考虑 $p_{k}$ 。

B1.2 $t_{2} p_{2}, t_{3} p_{2}$ 都不是G中的边。

在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}$ 选择在 $I_{i}$ 中，对于 $p_{k - 1}, p_{k}$ ，Painter优先考虑 $p_{k}$ 。

B2 不存在点 $w \in V (G) - V (P)$ 使得 $σ (v) = p_{k - 2}$ 。

B2.1 $t_{2} p_{2}, t_{3} p_{2}$ 中一个是G中的边。

我们假设 $t_{2} p_{2} \in E (G)$ 。在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

B2.2 $t_{2} p_{2}, t_{3} p_{2}$ 都不是G中的边。

在第i回合Lister选中一个未染顶点集 $L_{i}$ ，Painter按照以下策略选择 $I_{i}$ ：

1) 对于 $i = 1, 2, 3$ 有 $t_{i} \in L_{i}$ ，玩家Painter优先选择 $t_{i}$ 在 $I_{i}$ 中。

2) 如果 $L_{i} \subseteq S$ ，那么Painter按照顺序 $p_{1}, p_{2}, \dots, p_{k - 1}, p_{k}$ 选择在 $I_{i}$ 中。

3) 如果 $L_{i} ⊄ S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_{i}, p_{i + 1}, p_{i + 2}$ ，其中 $1 \leq i \leq k - 2$ 。如果 $p_{i}, p_{i + 1}, y \in L_{i}$ ，那么Painter优先考虑 $p_{i}, p_{i + 1}$ ；如果 $p_{i + 2}, y \in L_{i}$ ，那么玩家Painter优先考虑y。当y在P上的邻点是 $p_{k - 3}, p_{k - 2}, p_{k}$ 。如果 $p_{k - 3}, p_{k}, y \in L_{i}$ ，那么Painter优先考虑 $p_{k - 3}, p_{k}$ ；如果 $p_{k - 2}, y \in L_{i}$ ，Painter优先考虑y。

由以上的策略，S中的点一般只会因为它前面的邻点丢失1个筹码。只有当y在P上有三个邻点 $p_{i}, p_{i + 1}, p_{i + 2}$ 时， $p_{i + 2}$ 会因为y丢失3个筹码，根据引理12，y是唯一的，所以 $p_{i + 2}$ 最多丢失4个筹码， $p_{i + 2}$ 还有筹码可用。因此 $G [S]$ 是在线f-可选的。对于G中的点，我们需要说明 $(G^{'}, f^{'})$ 满足引理1的条件。由 $f^{'}$ 定义可知G中的点了y都有足够的筹码可用，因此我们只需要说明 $f^{'}$ 在 $G^{'}$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_{i}, p_{i + 1}$ 丢掉2个筹码，所以y在 $G^{'}$ 中至少有3个筹码。从而 $G - E (T)$ 在线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

期刊菜单