Operations Research and Fuzziology
Vol.08 No.02(2018), Article ID:24443,6
pages
10.12677/ORF.2018.82005
On-Line 4-Choosable Planar Graphs
Huihui Yan
Department of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 27th, 2018; accepted: Apr. 11th, 2018; published: Apr. 20th, 2018
ABSTRACT
On-line list coloring of a graph (is also called Painting Game) is an online version of list coloring. The on-line list coloring game on planar graph G is played by two players: Lister and Painter. We say G is on-line f-choosable if Painter has a winning strategy in this game. The on-line list coloring number of G is denoted by cp(G); it is the minimum positive integer k such that G is on-line k-choosable. This paper proves that the planar graphs containing no cycles of certain lengths k are on-line 4-choosable (or called 4-paintable) by using Alon-Tarsi Theorem, where k = 3, 4, 5 or 6.
Keywords:Planar Graph, Alon-Tarsi Theorem, Cycle, On-Line List Coloring
平面图的在线4列表染色
颜慧慧
浙江师范大学数理与信息工程学院,浙江 金华
收稿日期:2018年3月27日;录用日期:2018年4月11日;发布日期:2018年4月20日
摘 要
图的在线列表染色(也叫Painting博弈)是图的列表染色的在线版本,近年来得到广泛的研究。平面图G上的f列表染色游戏有两位玩家:Lister和Painter。如果Painter在图G上的f列表染色游戏中有一个赢的策略,我们说图G是在线f-可选的。如果图G是在线f可选的且f = 4,则称图G是在线4-可选的。图G的在线选择数用cp(G)表示,是最小的正整数k使得图G是在线k-可选的。本文结合Alon-Tarsi定理证明了当k = 3, 4, 5或6时,不含k圈的平面图是在线4-可选的(或叫4-可涂的)。
关键词 :平面图,Alon-Tarsi定理,圈,在线列表染色
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. 引言
图的染色是图论研究领域中相当活跃的一部分,也是非常重要的研究课题,其研究的问题来源于著名的四色猜想。如今,图的经典染色这一概念已经向很多方面进行推广和延伸,平面图的列表染色问题便是其中之一。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)。
文章引用
颜慧慧. 平面图的在线4列表染色
On-Line 4-Choosable Planar Graphs[J]. 运筹与模糊学, 2018, 08(02): 39-44. https://doi.org/10.12677/ORF.2018.82005
参考文献
- 1. Vizing, V.G. (1976) Vertex Colorings with Given Colors. Diskret. Analiz, 29, 3-10. (In Russian)
- 2. Erdős, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Congressus Numerantium, 26, 125-157.
- 3. Thomassen, C. (1994) Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, 62, 180-181. https://doi.org/10.1006/jctb.1994.1062
- 4. Gutner, S. (2008) The Complexity of Planar Graph Choosability. Discrete Mathematics, 159, 119-130. https://doi.org/10.1016/0012-365X(95)00104-5
- 5. Schauz, U. (2009) Mr. Paint and Mrs. Correct. Electronic Journal of Combinatorics, 16, 18.
- 6. Chang, T.P. and Zhu, X. (2012) On-Line 3-Choosable Planar Graphs. Taiwanese Journal of Mathematics, 16, 511-519. https://doi.org/10.11650/twjm/1500406598
- 7. Han, M. and Zhu, X. (2015) Locally Planar Graphs Are 5-Paintable. Elsevier Science Publishers B. V., Amsterdam.
- 8. Wang, W. and Lih, K.W. (2002) Choosability and Edge Choosability of Planar Graphs without Five Cycles. Applied Mathematics Letters, 15, 561-565. https://doi.org/10.1016/S0893-9659(02)80007-6
- 9. Juvan, M. and Mohar, B. (2002) Planar Graphs without Cycles of Specific Lengths. European Journal of Combinatorics, 23, 377-388. https://doi.org/10.1006/eujc.2002.0570
- 10. Zhu, X. (2009) On-Line List Colouring of Graphs. Electronic Journal of Combinatorics, 16, 3665-3677.
- 11. Lam, P.C.B., Xu, B. and Liu, J. (1999) The 4-Choosability of Plane Graphs without 4 Cycles. Journal of Combinatorial Theory, 76, 117-126. https://doi.org/10.1006/jctb.1998.1893
- 12. Alon, N. and Tarsi, M. (1992) Colorings and Orientations of Graphs. Combinatorica, 12, 125-134. https://doi.org/10.1007/BF01204715