Advances in Applied Mathematics
Vol.
12
No.
08
(
2023
), Article ID:
70528
,
7
pages
10.12677/AAM.2023.128351
平面图的无圈5-可选性
傅水苗
浙江师范大学数学科学学院,浙江 金华
收稿日期:2023年7月13日;录用日期:2023年8月3日;发布日期:2023年8月14日
摘要
假设 是图G的一个顶点染色。如果任意两个相邻的点染不同颜色,且每个圈至少使用三种颜色,则称 是一个无圈染色。如果对于G的任意的k-列表配置L,G有一个无圈L-染色,则称G是无圈k-可选的。本文证明了3圈不与 圈相邻和4圈不与 圈相邻的平面图是无圈5-可选的。
关键词
平面图,无圈染色,无圈可选性
Acyclic 5-Choosability of Planar Graph
Shuimiao Fu
College of Mathematics Science, Zhejiang Normal University, Jinhua Zhejiang
Received: Jul. 13th, 2023; accepted: Aug. 3rd, 2023; published: Aug. 14th, 2023
ABSTRACT
Let is a vertex coloring of graph G. The is acyclic if two adjacent vertices color with different colors and every cycle uses at least three colors. A graph G is k-acyclicallychoosable if G is acyclic L-list colorable for any list assignment L with for each . In this paper, we prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where if and if .
Keywords:Planar Graph, Acyclic Coloring, Acyclic Choosability
Copyright © 2023 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
设G是一个具有顶点集V(G)和边集E(G)的图。G的一个正常的k-染色是一个映射 : ,使得对于任何边 有 。如果每个圈使用至少三种颜色。则称 是一个无圈k-染色。如果G有一个无圈k-染色,则称G是一个无圈k-可染的。
1973年Grünbaum在文献 [1] 提出猜想:每个平面图都是无圈5-可染的。Borodin在文献 [2] 证明了Grünbaum的猜想。1976年,Kostochka等人在文献 [3] 证明了存在二部2-退化的平面图,它们不是无圈4-可染的。所以这个界5是最好的。
图G的一个列表配置L是为G的每个顶点v分配一个可选颜色集 。如果G有一个正常的染色 ,使得对每个顶点v, ,那么图G是L列表可染的。如果对每个顶点v, ,则称L是一个k-列表配置。如果对于G的任意的k-列表配置L,G都是L-可染的,则称G是k-可选的。如果对于G的任意的k-列表配置L,G有一个无圈L-染色,则称G是无圈k-可选的。G的无圈列表色数是使得G是无圈k可选的最小的整数k。对于平面图得可选性,我们可以知道以下一些结果。
因为每个子图都有一个最多为5度的顶点,所以每个平面图都是6-可选的,这是显然的。1993年Voigt在文献 [4] 中给出了一个不是4-可选的平面图的例子。之后Thomassen在文献 [5] 中证明了每个平面图都是5-可选的。这也就论证了平面图是5-可选的。通过平面图的可选性,下面扩展到无圈可选性。
对于列表无圈染色,早在2002年Borodin等人在文献 [6] 中证明了所有平面图都是无圈7-可选的,并提出了以下猜想:
猜想1 每个平面图都是无圈5-可选的。
这个猜想是困难的,关于这个猜想很多人做了尝试。在2011年之前,它只验证了几个限制类的平面图:围长至少5 [7] ,没有4和5圈,或没有4和6圈 [8] ,没有4圈和弦6圈 [9] ,没有4圈也没有两个3圈的距离小于3 [10] 。在所有这些结果中,长度为4的圈都是被禁止的。2011年,Borodin和Ivanova在文献 [11] 中证明了3圈不与 圈相邻和4圈不与 圈相邻的平面图是无圈5-可选的。2013年,Borodin等人在文献 [12] 中证明了没有4圈和5圈的平面图是无圈4-可选的。2014年,Wang等人在文献 [13] 中证明了4圈不与 圈相邻的平面图是无圈6-可选的。同年,Hou和Liu在文献 [14] 中证明了每个环形图是无圈8-可选的。2021年,Sun lin在在文献 [15] 中证明了没有5圈和相邻4圈的平面图是无圈6-可选的。本文在这些基础上进行了拓展:
定理1 3圈不与 圈相邻和4圈不与 圈相邻的平面图是无圈5-可选的。
本篇文章中所有的图都是有限简单图。对于一个平面图G, , , 是图G的点,边,面的集合。对于 , (或简单地用 来表示)表示v的邻居的集合,并且 (或简单地用 来表示)是v的度。假设 。如果两个圈或者面至少有一个公共点,那么我们说他们是相交的。如果两个圈或者面至少有一条公共边,那么我们说他们是相邻的。如果 是f上按照顺时针的顺序的边界上的点,那么我们用 去表示一个面f,并且允许有重复的点。一个面f的度是其边界漫游中的边步数,用 表示。一个k-点,k--点,或者k+-点是一个k度,至少k度,或者至多k度的点。我们同样可以定义k-面,k--面,k+-面。
对于 并且 , 表示与x相邻或者相关联的i-点的数量。如果一个点或者一条边与一个3-面相关联,那么它被称为三角形的。如果uv是一条不是三角形的边,并且u是一个三角形的3-点,那么称u是v的坏的邻居。
2. 定理1的证明
设G是定理1的极小反例,就是说对于 有一个 的列表配置L,使得G不是无圈L-染色,而对于 的任何子图 是无圈L-染色。显然,G是连通的并且没有1-点。
2.1. 极小反例的结构性质
以下极小反例的结构性质的证明在文献 [4] [5] [10] 中。
引理1 对于每个 ,G有以下性质。
(A1) 一个2-点不与一个4−-点相邻。
(A2) 如果 ,那么
(i) v没有坏的邻居,并且
(i) 如果v与一个3-点相邻,那么v不会与任何4−-点相邻。
(A3) 4-点没有坏的邻居。
(A4) 如果 ,那么
(i) ,并且
(i) 如果 ,那么v不会与任何三角形的3-点相邻。
(A5) 如果 ,那么
(i) ,而且
(i) 如果 ,那么v既不与一个3-点相邻也不与一个3-面相关联。
(A6) 如果 ,那么 。
(A7) 不会存在一个3-面 使得 , 和 。
2.2. 权转移
由欧拉公式 和公式 。我们可以得出
。
现在我们对每个 定义一个初始权重 ,设对每个 , ,每个 , 。我们将设计适当的权转移规则。由于权转移过程中,总的权值是固定的,如果我们将初始权值 改变为最终权值 ,使得对于每个 ,都满足 ,那么
。
这将是一个矛盾。这意味着定理中的反例不存在,因此定理成立。
权转移规则如下:
R1每个10+-面给3-面转权 。
R2每个2-点v的邻居给2-点$v$转权 ,并且如果v不与一个4-面相关联,那么与v相关联的5+-面给v转权 ,否则与v相关联的7+-面给v转权1。
如果5-面与一个2-点和两个非三角形的3-点相关联,那么我们称5-面是虚弱的。
R3如果5+-面是虚弱的,那么5+-面给每个相关联的非三角形的3-点转权 。如果3-点与4-面相关联,那么5+-面给每个相关联的非三角形的3-点转权 。如果3-点与其他面相关联,那么5+-面给每个相关联的非三角形的3-点转权 。
R4每个5-面给三角形的3-点转权 ,每个10+-面给三角形的3-点转权 。
R5 5+-点给每个相邻的三角形的3-点转权 。
R6如果5+-点与非三角形的3-点相邻,且非三角形的3-点与虚弱的5-面相关联,那么5+-点给非三角形的3-点转权 。
因为G中3圈不与 圈相邻和4圈不与 圈相邻,所以我们有如下命题。
命题1 1) 当5-面与3-面中的某一边相邻时,3-面的另外两边都与10+-面相邻。
2) 3-面不与6-面和8-面相邻。
3) 4-面与7+-面相邻。
下面将检验对于所有的 , 。
情况1: 。
在这种情况下,我们有 。根据引理1 (A1)和R2,则 。
情况2: 。
在这种情况下,我们有 。如果v与一个3-面uvw相关联并且与一个不是u,w的点z相邻,那么根据引理1 (A3), ,并且根据引理1 (A7),u,w中至少有一点的度大于等于5。由此 。如果v与一个4-面相关联,那么根据命题1和R3, 。如果v在虚弱的5-面的边界上,那么根据R3和R6, 。这是因为根据引理1 (F2),v至少跟两个5+-点相邻,因此v最多与两个虚弱的5-面相关联。否则, 。
情况3: 。
显然, 。
情况4: 。
在这种情况下, 。根据引理1 (A4),有 。如果 ,那么根据R5和R6, 。假设 ,根据引理1 (A4),$v$不与三角形的3-点相邻。因此根据R2和R6, 。
情况5: 。
当 时,根据引理1 (A5),有 。如果 ,那么根据引理1 (A5),v不与3-点相邻。则 。如果 ,那么 。
当 时,根据引理1 (A6),有 。则 。
当 时, 。
下面将检验对于所有的 , 。
情况1: 。
当 时,如果5-面与$f$相邻s,那么根据R1,有 。否则有 。
当 时,有 。
情况2: 。
在这种情况下, 。根据引理1 (A1),有 。如果 ,根据R2,那么 。如果 ,那么 。如果有两个3-点,根据R2,R3和R4,那么 。如果至多一个3-点,根据R2,R3和R4,那么 。如果 ,那么 。根据R2,R3和R4, 。
情况3: 。
为了估计f总的转权,我们将f的转权均匀地分配给f的边界中最接近转权接受者的边中的相关联的小于等于的3个顶点和相邻的3个面。
已知通过R2一个2-点最多从f得到权重1,通过R3和R4一个3-点最多从f得到权重 ,f最多给每个相邻的3-面转权 。
很容易看出,来自f的每个权中的接收者都恰好属于以下三种类型的一条路径P,其中指数取模 :
i) ,其中 , , ,并且 是非三角形的;
ii) ,其中 和 是非三角形的, , , ;
iii) 极大序列 由三角形边组成,其中 ,由(非三角形)边 或 扩张当且仅当 或者 。
设P由l(P)条边组成,并通过R1~R3导致f的总转权m(P)。如果P是类型iii),则 ,这意味着P的每条边在平均后从f中转权 得到。如果P的类型是ii),那么 并且 ,所以P的每条边平均从f中最多得到 。
假设P的类型是i);然后是 并且 ;所以P的每条边从f中最多得到 。此外,当且仅当 并且 与4-面相关联时, 。否则, ,所以P的两条边从f中得到 。
由于我们的反例G的结构性质A1~A7,f的边界中的每条边最多属于一条i)~iii)类型的路径。
如果 ,那么根据定理1的假设,具有 的路径P是不可能的,所以 。
如果 ,那么f具有 的路径P最多有3条。当 的路径P最多有2条时, 。当 的路径P有3条时, 。
如果 ,那么 。
如果 ,那么我们记类型(i)的路径的总边数为 ,类型(ii)的路径的总边数为 ,类型iii)的路径的总边数为 。则我们有 。所以
定理1证毕。
3. 总结与展望
本文采用定理证明与权转移相结合的方法证明定理。权转移方法是图的染色理论中常用的证明方法之一,权转移方法经常结合其他方法和技术,如组合数学中的一些组合方法,在证明很多与染色问题有关的命题时,应用非常广泛,方法非常巧妙。当然该方法也有局限性,对于权转移的讨论过程比较繁琐。本文对于平面图是无圈5-可选的猜想更进了一步,允许了4-圈存在,图类更加广泛。在今后的研究中将会继续专研平面图是无圈5-可选的猜想,证明方法进一步改进,减少繁琐的过程,尽量精简过程。
文章引用
傅水苗. 平面图的无圈5-可选性
Acyclic 5-Choosability of Planar Graph[J]. 应用数学进展, 2023, 12(08): 3530-3536. https://doi.org/10.12677/AAM.2023.128351
参考文献
- 1. Grünbaum, B. (1973) Acyclic Colorings of Planar Graphs. Israel Journal of Mathematics, 14, 390-408. https://doi.org/10.1007/BF02764716
- 2. Borodin, O.V. (1979) On Acyclic Colorings of Planar Graphs. Discrete Mathematics, 25, 211-236. https://doi.org/10.1016/0012-365X(79)90077-3
- 3. Kostochka, A.V. and Mel’nikov, L.S. (1976) Note to the Pa-per of Grünbaum on Acyclic Colorings. Discrete Mathematics, 14, 403-406. https://doi.org/10.1016/0012-365X(76)90075-3
- 4. Voigt, M. (1993) List Colorings of Planar Graph. Discrete Mathematics, 120, 215-219. https://doi.org/10.1016/0012-365X(93)90579-I
- 5. Thomassen, C. (1994) Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, Series B, 62, 180-181. https://doi.org/10.1006/jctb.1994.1062
- 6. Borodin, O.V., Fon-Der-Flaass, D.G., Kostochka, A.V., Raspaud, A. and Sopena, E. (2002) Acyclic List 7-Coloring of Planar Graphs. Journal of Graph Theory, 40, 83-90. https://doi.org/10.1002/jgt.10035
- 7. Montassier, M., Ochem, P. and Raspaud, A. (2006) On the Acyclic Choosa-bility of Graphs. Journal of Graph Theory, 51, 281-300. https://doi.org/10.1002/jgt.20134s
- 8. Montassier, M., Raspaud, A. and Wang, W. (2007) Acyclic 5-Choosability of Planar Graphs without Small Cycles. Journal of Graph Theory, 54, 245-260. https://doi.org/10.1002/jgt.20206
- 9. Zhang, H. and Xu, B. (2009) Acyclic 5-Choosable Planar Graphs with Neither 4-Cycles nor Chordal 6-Cycles. Discrete Mathematics, 309, 6087-6091. https://doi.org/10.1016/j.disc.2009.05.018
- 10. Chen, M. and Wang, W. (2008) Acyclic 5-Choosability of Planar Graphs without 4-Cycles. Discrete Mathematics, 308, 6216-6225. https://doi.org/10.1016/j.disc.2007.11.076
- 11. Borodin, O.V. and Ivanova, A.O. (2011) Acyclic 5-Choosability of Planar Graphs without Adjacent Short Cycles. Journal of Graph Theory, 68, 169-176. https://doi.org/10.1002/jgt.20549
- 12. Borodin, O.V. and Ivanova, A.O. (2013) Acyclic 4-Choosability of Planar Graphs with no 4- and 5-Cycles. Journal of Graph Theory, 72, 374-397. https://doi.org/10.1002/jgt.21647
- 13. Wang, W.F., Zhang, G. and Chen, M. (2014) Acyclic 6-Choosability of Planar Graphs without Adjacent Short Cycles. Science China Mathematics, 57, 197-209. https://doi.org/10.1007/s11425-013-4572-6
- 14. Hou, J.F. and Liu, G.Z. (2014) Every Toroidal Graph Is Acycli-cally 8-Choosable. Acta Mathematica Sinica, English Series, 30, 343-352. https://doi.org/10.1007/s10114-013-1497-5
- 15. Sun, L. (2021) Acyclic 6-Choosability of Planar Graphs without 5-Cycles and Adjacent 4-Cycles. Acta Mathematica Sinica, English Series, 37, 992-1004. https://doi.org/10.1007/s10114-021-9335-7