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的一个映射 f : V ( G ) N 。G的f-列表配置是给图G的点集合的列表配置L,每个点v有一个颜色集合 L ( v ) ,集合 L ( v ) f ( v ) 个颜色。对于G的列表配置L,我们说G是L-可染的如果存在G的一个真染色f使得对于任意一个顶点v,都有 ϕ ( v ) L ( v ) 。图G的染色数用 χ ( G ) 表示,是指最小的正整数k使得图G是k-可染的。如果对于G的任意一个f-列表配置L,图G是L可染的,则称图G是f-可选的。如果图G是f-可选的,当f是一个常数函数即 f k 时,我们就说G是k-可选。图G的选择数用 χ l ( G ) 表示,是指最小的正整数k使得图G是k-可选的。

关于平面图的可选性问题,1979年Erdős [2] 等人全面分析了2-可选图。1994年,Thomassen [3] 证明了每一个平面图都是5-可选的。对于一个给定的图能否判断出是3-可选或4-可选的还未解决。1996年,Gutner [4] 证明了这些问题是NP-困难的。

Schauz [5] 于2009年在图的列表染色基础上,介绍了一种新型动态列表染色方法——图的在线列表染色。定义如下。

定义1:设图G的一个映射 f : V ( G ) N 。图G上的f列表染色游戏定义如下:该游戏有两位玩家:Lister和Painter。起初,图G中所有点均未被染色,且任意顶点v有 f ( v ) 个筹码。在任意一个回合,Lister选择图G中未染色顶点集的一个非空子集M,M中每一个顶点减少一个筹码。Painter选择M中一个独立集I且I中的顶点被染色。若某一回合后,存在一个点v未被染色且没有筹码了,则Lister赢得比赛。若某一回合后,所有点均被染色了,则Painter赢得比赛。

定义2:设映射 f : V ( G ) N 。如果Painter在图G上的f列表染色游戏中有一个赢的策略,我们称图G是在线f可选的。如果图G是在线f可选的且常数函数 f = k (k是常数),则称图G是在线k-可选的。图G的在线选择数用 χ p ( G ) 表示,是指最小的正整数k使得G是在线k-可选的。

由列表染色的定义和在线列表染色的定义易知,若平面图G是在线f-可选的,则图G是f-可选的,因此有 χ ( G ) χ p ( G ) 。在另一方面, χ p ( G ) χ ( G ) 这一差值也可以任意大。

关于平面图的在线可选性问题,2012年,Chang和Zhu [6] 证明了若G是不含3圈的平面图,且没有4圈与4圈或4圈与5圈相邻,则图是G在线3-可选的。2015年,Han和Zhu [7] 证明了局部平面图是在线5-可选的。

本文,我们研究的图均为有限,简单(无环,无重边)图。设G是一个平面图, V ( G ) 是图G的顶点集, E ( G ) 是图G的边集, | E ( G ) | 表示边集的大小。 d G ( x ) 表示顶点x在图中G的度。令 Δ ( G ) δ ( G ) 分别图G的最大度和最小度, Δ + ( G ) 表示图G的最大出度。对于 S V ( G ) ,我们令 G [ S ] 表示由S诱导的子图。图G是d-退化的若图G的每一个子图H有一个顶点的度在图H中至多为d。易知每一个d-退化的图是 ( d + 1 ) -可选的。

2. 不含3, 5或6圈的平面图

使用欧拉公式可知,不含3圈的平面图是3-退化的。2002年Wang和Lih [8] [9] 证明了不含5圈的平面图是3-退化的。同年,Juvan和Mohar [9] 证明了不含6圈的平面图是3-退化的。于是我们有了下面的定理3。

定理3: [8] [9] 令k是一个整数,其中 k = 3 , 5 或6。若平面图G不含k圈,则图G是3-退化的。

下面我们将给出本节要证的主要结论,即下述定理4。

定理4:令k是一个整数,其中 k = 3 , 5 或6。若平面图G不含k圈,则图G是在线4-可选的。

为证明定理4,需要下述几个引理的支持。引理5是证明在线列表染色问题中一个非常有用的命题, [10] 中的推论8是比引理5更强的结论且已被证明。这里我们重新说明一下引理5的证明,后面我们将利用引理5证明引理6。

引理5:设A是一个集合,其中 A = { x | f ( x ) > deg G ( x ) } 。若 G A 是在线f可选的,则图G是在线f-可选的。

证明:因为 G A 是在线f-可选的,所以Painter在 G A 上有一个赢的策略。

首先,Lister选择 V ( G ) 的任意一个顶点子集X,然后Painter按照赢的策略先将 ( G A ) X 中的顶点染好颜色。接下来Painter染 A X 中的顶点。对于 A X 中的顶点,Painter需要一个一个的查看,查看 A X 中的顶点有没有邻点被染色的。若 A X 中的顶点的邻点未被染色,则将该点染色;若 A X 中的顶点的邻点被染色,则该顶点不染色且失去一个筹码。也就是说,若存在某个顶点u, u A X ,顶点u的筹码数减少1,但顶点u未被染色,则说明u的邻点被染色了。当u的邻点都已染好时,因为 f ( u ) > d G ( u ) ,所以在剩余的图中,顶点u的筹码数总是大于0的,即游戏这样进行下去, A X 中的点都会被染色。所以Painter在图G有一个赢的策略,即图G是在线f-可选的。 □

引理6:若平面图G是3-退化的,则图G是在线4-可选的。

证明:对图G的点数作归纳法。设v是图G中一个度数小于等于3的顶点,即 d G ( v ) 3 ,由归纳法假设可知, G v 是3-退化的,则 G v 是在线4-可选的。设集合 A = { v } ,因此由引理5可知,图G是在线4-可选的。 □

由定理3和引理6易知,定理4成立。

3. 不含4圈的平面图

Lam,Xu和Liu在 [11] 证明了不含4圈的平面图是4-可选的,即下述定理7。

定理7: [11] 不含4圈的平面图是4-可选的。

[11] 中令 F 5 3 表示一个特殊的不含4圈的平面图,即 F 5 3 是由一个5面和一个外部相邻三角形组成的。令H是图G的一个子图,若H同构于 F 5 3 且对于任意 v V ( H ) 都有 d G ( v ) = 4 ,则H叫做 F 5 3 -子图。

引理8: [11] 设图G是不含4面且不含相邻三角形的平面图。若 δ ( G ) = 4 ,则图G包含一个 F 5 3 -子图。

易知,若一个图不含4圈,则该图不含4面且不含有相邻三角形。本节我们主要证明下述定理9。

定理9:若平面图G不含4圈,则图G是在线4-可选的。

显然定理9是定理7的在线版本,是比定理7更强的结论。对于定理9的证明,我们采用Alon和Tarsi [12] 的方法,找到图G的一个好的定向。在证明主要结论之前,我们先给出一些已知定义及结论,以便我们的证明。

3.1. 已有结论简介

假设D是图G的定向图,用 E ( D ) 表示在D中已定向的边或弧的集合。若 ( x , y ) E ( D ) ,则x是y的入邻点且y是x的出邻点。顶点v的出度 d D + ( v ) 和入度 d D ( v ) 分别是顶点v在定向图D中出邻点的个数和入邻点的个数。

D 是D的一个子图,若对于D中的每一个顶点v,有 d D + ( v ) = d D ( v ) ,则 D 是一个欧拉子图。若 | E ( D ) | 是奇数,则 D 是奇的欧拉子图;若 | E ( D ) | 是偶数,则 D 是偶的欧拉子图。令 E E ( D ) 表示D的偶的欧拉子图的集合, O E ( D ) 表示D的奇的欧拉子图的集合。设

d i f f ( D ) = | E E ( D ) | | O E ( D ) | (1)

d i f f ( D ) 0 ,则我们称D是图G的一个好的定向图。

Alon和Tarsi [12] 的下述结论是研究列表染色的一个强有力的工具,称为Alon-Tarsi定理。

Alon-Tarsi定理 [12] 若D是图G的一个好的定向图,且对任意顶点v都有 f ( v ) = d D + ( v ) + 1 ,则图G是f-可选的。

Schauz [5] 将Alon-Tarsi定理延拓至在线列表染色的研究,即下述定理10。

定理10: [5] 若D是图G的一个好的定向图,且对任意顶点v都有 f ( v ) = d D + ( v ) + 1 ,则图G是在线f-可选的。

3.2. 证明定理12

下面我们将给出强的定向图的定义,显然定义11是比好的定向图更强的定义。

定义11:设X是 V ( G ) 的一个子集。 D G [ X ] 的一个定向图,如果下列条件成立:

1) d i f f ( D ) 0

2) 对于每一个顶点 v X ,有 d D + ( v ) 3 ( d G ( v ) d G [ X ] ( v ) )

我们称 D G [ X ] 的一个强的定向图。

如果 G [ X ] 有一个强的定向图,我们称子图 G [ X ] 是可约的。

定理12:若图G是不含4圈的平面图,则图G有一个 Δ + ( D ) 3 的好的定向图D。

本文通过证明定理12的成立来说明定理9是成立的。采用反证法,首先假设定理12是错误的,且图G是关于最小度的极小反例。我们建立一些极小反例的性质。

引理13:图G不含可约结构。

证明:假设 D G [ X ] 的一个强的定向图,那么 d i f f ( D ) 0 。由图G的极小性可知, G X 有一个 Δ + ( D ) 3 的好的定向图 D ,那么 d i f f ( D ) 0 。令D是G的定向图,其中D是 D D 的并,定向图D是把X和 V X 之间的所有边定向为从X指向 V X 。因为X和 V X 之间所有边均是从X指向 V X 的,所以D的任何欧拉子图都不含有从X指向 V X 的边。那么

d i f f ( D ) = | E E ( D ) | | O E ( D ) | = ( | E E ( D ) E E ( D ) | + | O E ( D ) O E ( D ) | ) ( | E E ( D ) O E ( D ) | + | O E ( D ) E E ( D ) | ) = | E E ( D ) | ( | E E ( D ) | | O E ( D ) | ) | O E ( D ) | ( | E E ( D ) | | O E ( D ) | ) = | E E ( D ) | d i f f ( D ) | O E ( D ) | d i f f ( D ) = d i f f ( D ) ( | E E ( D ) | | O E ( D ) | ) = d i f f ( D ) d i f f ( D ) 0

综上,我们可知 d i f f ( D ) = d i f f ( D ) d i f f ( D ) 0 。因为对于每个顶点 v X ,都有 d D + ( D ) 3 ( d G ( v ) d G [ X ] ( v ) ) ,因此 Δ + ( D ) 3 。这与图G是极小反例是矛盾的。□

Figure 1. The orientation of G [ H ]

图1. G [ H ] 的定向图

下面我们给出定理12的证明过程。

证明:假设图G是关于最小度的极小反例,则 δ ( G ) = 4 。因为图G不含4圈,所以G不含4面且不含相邻三角形。由引理8可知,G有一个 F 5 3 -子图H,其中 V ( H ) = { u 1 , , u 6 } E ( H ) = { u 1 u 2 , u 2 u 3 , u 3 u 4 , u 4 u 5 , u 5 u 6 , u 6 u 1 , u 2 u 6 } 。令 f ( v ) 是图G的筹码数,对于每一个点 v V ( G ) ,有 f ( v ) = 4 。由图G的极小性可知, G H 是在线4-可选的。令 f ( v i ) 表示点 v i 可用的筹码数,则对于 i = 1 , 3 , 4 , 5 ,有 | f ( u i ) | 2 ,对于 i = 2 , 6 ,有 | f ( u i ) | 3 。假设当 i = 1 , 3 , 4 , 5 | f ( u i ) | = 2 ;当 i = 2 , 6 | f ( u i ) | = 3 。如图1所示,构造 G [ H ] 的一个强的定向图 D ,易知对于每一个顶点 v H ,有 d D + ( D ) 3 ( d G ( v ) d G [ H ] ( v ) ) d i f f ( D ) = 1 ,即 G [ H ] 是可约结构,这与引理13矛盾。 □

上述我们完成了定理12的证明,也就证明了定理9是成立的,即不含4圈的平面图是在线4-可选的。结合第二节我们可以得到下述定理14。

定理14:当 k = 3 , 4 , 5 或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. 1. Vizing, V.G. (1976) Vertex Colorings with Given Colors. Diskret. Analiz, 29, 3-10. (In Russian)

  2. 2. Erdős, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Congressus Numerantium, 26, 125-157.

  3. 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. 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. 5. Schauz, U. (2009) Mr. Paint and Mrs. Correct. Electronic Journal of Combinatorics, 16, 18.

  6. 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. 7. Han, M. and Zhu, X. (2015) Locally Planar Graphs Are 5-Paintable. Elsevier Science Publishers B. V., Amsterdam.

  8. 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. 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. 10. Zhu, X. (2009) On-Line List Colouring of Graphs. Electronic Journal of Combinatorics, 16, 3665-3677.

  11. 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. 12. Alon, N. and Tarsi, M. (1992) Colorings and Orientations of Graphs. Combinatorica, 12, 125-134. https://doi.org/10.1007/BF01204715

期刊菜单