含有交叉数的图的在线列表染色

Online List Colouring of Graphs with Crossing Number

摘要: 在线列表染色概念是由U. Schauz 和X. Zhu 于2009年分别提出。在线列表染色概念提出以来，不少学者研究了相关图的在线列表染色。例如，U. Schauz 证明了平面图是在线5-可选的，M. Han和X. Zhu 证明了局部平面图是在线5-可选的，M. Han和X. Zhu 证明了每个平面图是1-缺陷在线(9,2)可选的，等相关性成果。在本文中我们证明了含有至多一个交叉的图是在线5-可选的。

Abstract: The concept of online list colouring was introduced in 2009 by U. Schauz  and independently by X. Zhu . 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  has proved that each planar graph is online 5-paintable; M. Han and X. Zhu  have proved that locally planar graphs are 5-paintable; M. Han and X. Zhu  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.

1. 引言

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

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

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

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

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

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

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

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

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

2. 主要引理

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

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

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

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

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

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

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

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

1) Painter从 $V\left(S\right)\cap L_i$ 中选出一个独立集 $I_S$ 。

2) Painter从 $V\left(G^{\prime }\right)\cap \left(L_i-I_S\right)$ 中选出一个独立集 $I_{G^{\prime }}$ 。

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

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

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

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

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

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

3. 极小反例的性质

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

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

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

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

引理2： $cr\left(G\right)=1$ 。

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

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

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

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

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

证明：假设G存在一个分离三圈 $C=xyz$ 且令 $G^{*}=\mathrm{int}\left[C\right]$ 。

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

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

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

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

令 $X=\left\{x_1,x_2,x_3,x_4\right\}$ ，且边 $e=x_1{x}_3$ 和 $e^{\prime }=x_2{x}_4$ 相互交叉。因为我们假设G的边数尽可能的多，所以我们可假设 $G\left[X\right]$ 是一个完全图。

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

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

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

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

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

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

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

证明：假设 $t_1{x}_1$ 是G中的一条边。根据引理6以及 $x_2$ 和 $x_4$ 之间的对称性，我们假设 $t_1{x}_4$ 不是G中的边。令 $S=\left\{t_1,x_1,x_2\right\}$ 。

情形1：G中不存在点w与 $t_1,x_1,x_2$ 都相邻。

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

情形2：G中存在点点w与 $t_1,x_1,x_2$ 都相邻。

根据引理6，我们有 $t_1{x}_3$ 不是G中的一条边，从而 $w\ne t_3$ 。由于我们的假设 $t_1{x}_4$ 不是G中的边，所以 $w\ne x_4$ 。根据引理7，对于 $i=2,3$ 我们有 $x_2{t}_i$ 不是G中的边。根据引理4，我们有 $t_3{x}_1$ 不是G中的边，并且w是唯一的。令 $G^{\prime }=G-S$ ，以及 $f^{\prime }$ 是 $V\left(G^{\prime }\right)$ 到N上的一个映射且满足对于 $v\in V\left(G^{\prime }\right)-\left\{w\right\}$ 都有 $f^{\prime }\left(v\right)=f\left(v\right)-\left|N_G\left(v\right)\cap S\right|$ 以及对于 $i=2,3$ 有 $f^{\prime }\left(t_i\right)=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\not\subset S$ 。玩家Painter一般优先考虑S中的点以及当 $x_2,w\in L_i$ ，Painter优先考虑w。当 $x_1,w\in L_i$ 时，此时我们需要考虑两种特殊情况：1) $t_2{x}_1\in E\left(G\right)$ ，那么根据引理4，我们有 $t_{2}w\notin E\left(G\right)$ 。如果 $t_2,x_1,w\in L_i$ ，Painter优先考虑 $t_2,w$ ；2) $t_2{x}_1\notin E\left(G\right)$ Painter优先考虑 $x_1$ 。

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

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

引理10：如果 $p_i,p_j$ 是 $v\in V\left(G\right)-V\left(P\right)$ 的邻点，那么 $\left|i-j\right|\le 2$ 。

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

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

证明：假设存在 $v\in V\left(G\right)-V\left(P\right)$ 在P上有四个邻点。根据引理10以及P的选择，这四个邻点是 $p_{k-3},p_{k-2},p_{k-1},p_k$ 。由于 $p_1{p}_2\cdots p_{k-3}v{p}_k{p}_{k-1}$ 的跨度不小于P的跨度，所以 $p_{k-2}{p}_k\in E\left(G\right)$ 。我们有 $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-\left\{p_{k-1},p_k\right\}$ 在P上有两个邻点。对于每个点 $V\left(G\right)-V\left(P\right)$ ，如果v在P上有三个点，那么令 $\sigma \left(v\right)=p_i$ ，其中 $p_i$ 是v在P上下标最大的邻点；如果v在P上最多两个邻点，那么令 $\sigma \left(v\right)=v$ 。

引理12：如果 $u\ne v$ ，那么 $\sigma \left(u\right)\ne \sigma \left(v\right)$ 。

证明：如果 $u\ne v$ 且 $\sigma \left(u\right)=\sigma \left(v\right)=p_i$ ，那么 $u,v$ 在P上都有三个邻点。如果 $p_i\ne p_k$ ，那么 $d_G\left(p_{i-1}\right)\le 4$ ，从而产生矛盾。因此 $p_i=p_k$ 。由于P的选择，所以 $u,v$ 邻点在 $\left\{p_{k-3},p_{k-2},p_{k-1},p_k\right\}$ 中。根据引理4， $u,v$ 不会都与 $p_{k-1}$ 相邻。不失一般性我们假设 $u{p}_{k-1}\notin E\left(G\right)$ 。因此u的邻点是 $p_{k-3},p_{k-2},p_k$ 。根据引理7，我们得出 $v{p}_{k-1}\notin E\left(G\right)$ 。这样 $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\left(P\right)$ 。令 $G^{\prime }=G-S$ ，以及 $f^{\prime }$ 是 $V\left(G^{\prime }\right)$ 到N上的一个映射且满足对于 $v\in V\left(G^{\prime }\right)$ 都有 $f^{\prime }\left(v\right)=f\left(v\right)-\left|N_G\left(v\right)\cap S\right|$ 除了那些在S上有三个邻点的点，以及对于 $i=2,3$ ， $f^{\prime }\left(t_i\right)=1$ 。

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

1.1 $t_2{p}_2,t_3{p}_2$ 中一个是G中的边。

我们假设 $t_2{p}_2\in E\left(G\right)$ 。在第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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $2\le i\le 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\left(G\right)$ 以及根据引理4，我们有 $t_{2}y\notin E\left(G\right)$ 。如果 $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\left[S\right]$ 是在线f-可选的。对于G中的点，我们需要说明 $\left(G^{\prime },f^{\prime }\right)$ 满足引理1的条件。由 $f^{\prime }$ 定义可知G中的点除了y都有足够的筹码可用，因此我们只需要说明 $f^{\prime }$ 在 $G^{\prime }$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_i,p_{i+1}$ 丢掉2个筹码，所以y在 $G^{\prime }$ 中至少有3个筹码。从而 $G-E\left(T\right)$ 在线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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $1\le i\le 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。

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

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

A 不存在点 $v\in V\left(G\right)-V\left(P\right)$ 使得 $\sigma \left(v\right)=p_k$ 。

A1 $t_2{p}_2,t_3{p}_2$ 中一个是G中的边。

我们假设 $t_2{p}_2\in E\left(G\right)$ 。在第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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $2\le i\le 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\left(G\right)$ 以及根据引理4，我们有 $t_{2}y\notin E\left(G\right)$ 。如果 $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\left[S\right]$ 是在线f-可选的。对于G中的点，我们需要说明 $\left(G^{\prime },f^{\prime }\right)$ 满足引理1的条件。由 $f^{\prime }$ 定义可知G中的点除了y都有足够的筹码可用，因此我们只需要说明 $f^{\prime }$ 在 $G^{\prime }$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_i,p_{i+1}$ 丢掉2个筹码，所以y在 $G^{\prime }$ 中至少有3个筹码。从而 $G-E\left(T\right)$ 在线f -可选的，与G是反例相矛盾。

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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $1\le i\le 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。

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

B 存在点 $v\in V\left(G\right)-V\left(P\right)$ 使得 $\sigma \left(v\right)=p_k$ 。

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

B1.1 $t_2{p}_2,t_3{p}_2$ 中一个是G中的边。

我们假设 $t_2{p}_2\in E\left(G\right)$ 。在第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,\cdots ,p_{k-1}$ 选择在 $I_i$ 中，对于 $p_{k-1},p_k$ ，Painter优先考虑 $p_k$ 。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $2\le i\le 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\left(G\right)$ 以及根据引理4，我们有 $t_{2}y\notin E\left(G\right)$ 。如果 $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\left[S\right]$ 是在线f-可选的。对于G中的点，我们需要说明 $\left(G^{\prime },f^{\prime }\right)$ 满足引理1的条件。由 $f^{\prime }$ 定义可知G中的点除了y都有足够的筹码可用，因此我们只需要说明 $f^{\prime }$ 在 $G^{\prime }$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_i,p_{i+1}$ 丢掉2个筹码，所以y在 $G^{\prime }$ 中至少有3个筹码。从而 $G-E\left(T\right)$ 在线f-可选的，与G是反例相矛盾。

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,\cdots ,p_{k-1}$ 选择在 $I_i$ 中，对于 $p_{k-1},p_k$ ，Painter优先考虑 $p_k$ 。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $1\le i\le 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。

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

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

B2.1 $t_2{p}_2,t_3{p}_2$ 中一个是G中的边。

我们假设 $t_2{p}_2\in E\left(G\right)$ 。在第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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $2\le i\le 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\left(G\right)$ 以及根据引理4，我们有 $t_{2}y\notin E\left(G\right)$ 。如果 $t_2,p_2,y\in L_i$ ，那么Painter优先考虑 $t_2,y$ ；如果 $p_2,y\in L_i$ ，Painter优先考虑 $p_2$ 。当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\left[S\right]$ 是在线f-可选的。对于G中的点，我们需要说明 $\left(G^{\prime },f^{\prime }\right)$ 满足引理1的条件。由 $f^{\prime }$ 定义可知G中的点除了y都有足够的筹码可用，因此我们只需要说明 $f^{\prime }$ 在 $G^{\prime }$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_i,p_{i+1}$ 丢掉2个筹码，所以y在 $G^{\prime }$ 中至少有3个筹码。从而 $G-E\left(T\right)$ 在线f-可选的，与G是反例相矛盾。

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,\cdots ,p_{k-1},p_k$ 选择在 $I_i$ 中。

3) 如果 $L_i\not\subset S$ ，玩家Painter一般优先考虑S中的点。当y在P上的邻点是 $p_i,p_{i+1},p_{i+2}$ ，其中 $1\le i\le 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\left[S\right]$ 是在线f-可选的。对于G中的点，我们需要说明 $\left(G^{\prime },f^{\prime }\right)$ 满足引理1的条件。由 $f^{\prime }$ 定义可知G中的点了y都有足够的筹码可用，因此我们只需要说明 $f^{\prime }$ 在 $G^{\prime }$ 中至少有3个筹码可用。根据以上的策略，点y最多因为 $p_i,p_{i+1}$ 丢掉2个筹码，所以y在 $G^{\prime }$ 中至少有3个筹码。从而 $G-E\left(T\right)$ 在线f-可选的，与G是反例相矛盾。

致谢

感谢浙江师范大学“千人计划”朱绪鼎教授对本文的帮助，也感谢所有匿名审稿人对本文的指导意见。

基金项目

国家自然科学基金项目资助(CNSF 00571319)。