平面图的无圈5-可选性.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2023,12(8),3530-3536 Published Online August 2023 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2023.128351 文章引用文章引用:傅水苗.平面图的无圈 5-可选性J.应用数学进展,2023,12(8):3530-3536.DOI:10.12677/aam.2023.128351 平面图的无圈平面图的无圈5-可选性可选性 傅水苗傅水苗 浙江师范大学数学科学学院，浙江 金华 收稿日期：2023年7月13日；录用日期：2023年8月3日；发布日期：2023年8月14日 摘摘 要要 假设假设 是图是图G的一个顶点染色。如果任意两个相邻的点染不同颜色，且每个圈至少使用三种颜色，则称的一个顶点染色。如果任意两个相邻的点染不同颜色，且每个圈至少使用三种颜色，则称 是一个无圈染色。如果对于是一个无圈染色。如果对于G的任意的的任意的k-列表配置列表配置L，G有一个无圈有一个无圈L-染色，则称染色，则称G是无圈是无圈k-可选的。本文可选的。本文证明了证明了3圈不与圈不与()i i=3,7,9圈相邻和圈相邻和4圈不与圈不与()jj36圈相邻的平面图是无圈圈相邻的平面图是无圈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 differ-ent colors and every cycle uses at least three colors.A graph G is k-acyclicallychoosable if G is acyc-lic L-list colorable for any list assignment L with()L vk for each()vV G.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,wherej=3,7,9 if i=3 and j36 ifi=4.Keywords Planar Graph,Acyclic Coloring,Acyclic Choosability 傅水苗 DOI:10.12677/aam.2023.128351 3531 应用数学进展 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-染色是一个映射：()1,2,V Gk，使得对于任何边()xyE G有()()xy。如果每个圈使用至少三种颜色。则称是一个无圈 k-染色。如果 G 有一个无圈 k-染色，则称 G 是一个无圈 k-可染的。1973 年 Grnbaum 在文献1提出猜想：每个平面图都是无圈 5-可染的。Borodin 在文献2证明了Grnbaum 的猜想。1976 年，Kostochka 等人在文献3证明了存在二部 2-退化的平面图，它们不是无圈4-可染的。所以这个界 5 是最好的。图G的一个列表配置L是为G的每个顶点v分配一个可选颜色集()L v。如果G有一个正常的染色，使得对每个顶点 v，()()xL x，那么图 G 是 L 列表可染的。如果对每个顶点 v，()L vk，则称 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 圈不与()35ii 圈相邻和 4 圈不与()46jj圈相邻的平面图是无圈 5-可选的。2013 年，Borodin 等人在文献12中证明了没有 4 圈和 5 圈的平面图是无圈 4-可选的。2014 年，Wang 等人在文献13中证明了 4 圈不与()3,4,5,6i i=圈相邻的平面图是无圈 6-可选的。同年，Hou 和 Liu 在文献14中证明了每个环形图是无圈 8-可选的。2021 年，Sun lin 在在文献15中证明了没有 5 圈和相邻 4 圈的平面图是无圈 6-可选的。本文在这些基础上进行了拓展：定理定理 1 3 圈不与()3,7,9i i=圈相邻和 4 圈不与()36jj圈相邻的平面图是无圈 5-可选的。本篇文章中所有的图都是有限简单图。对于一个平面图 G，()V G，()E G，()F G是图 G 的点，边，面的集合。对于()vV G，()GNv(或简单地用()N v来表示)表示 v 的邻居的集合，并且()()GGdvNv=(或简单地用()d v来表示)是 v 的度。假设()GGNvNvx=。如果两个圈或者面至少有一个公共点，那么我们说他们是相交的。如果两个圈或者面至少有一条公共边，那么我们说他们是相邻的。如果12,nu uu是 f 上按照顺时针的顺序的边界上的点，那么我们用12nu uu去表示一个面 f，并且允许有重复的点。一个面 f 的度是其边界漫游中的边步数，用()Gdf表示。一个 k-点，k-点，或者k+-点是一个 k 度，至少 k 度，或者至多 k 度的点。我们同样可以定义 k-面，k-面，k+-面。对于()()xV GF G并且2i，()in x表示与 x 相邻或者相关联的 i-点的数量。如果一个点或者一Open AccessOpen Access傅水苗 DOI:10.12677/aam.2023.128351 3532 应用数学进展 条边与一个 3-面相关联，那么它被称为三角形的。如果 uv 是一条不是三角形的边，并且 u 是一个三角形的 3-点，那么称 u 是 v 的坏的邻居。2.定理定理 1 的证明的证明 设 G 是定理 1 的极小反例，就是说对于()vV G有一个()5L v 的列表配置 L，使得 G 不是无圈 L-染色，而对于()()VGV G。如果v与一个4-面相关联，那么根据命题1和R3，()()1202ch vch v+。如果 v 在虚弱的 5-面的边界上，那么根据 R3 和 R6，()()111220834ch vch v+。这是因为根据引理 1(F2)，v 至少跟两个 5+-点相邻，因此 v 最多与两个虚弱的 5-面相关联。否则，()()1303ch vch v+=。情况情况 3：()4d v=。显然，()()0ch vch v=。情况情况 4：()5d v=。在这种情况下，()541ch v=。根据引理 1(A4)，有()21nv。如果()20nv=，那么根据 R5 和R6，()()1506ch vch v。假设()21nv=，根据引理 1(A4)，$v$不与三角形的 3-点相邻。因此根据R2 和 R6，()()114082ch vch v=。情况情况 5：()6d v。当()6d v=时，根据引理 1(A5)，有()24nv。如果()24nv=，那么根据引理 1(A5)，v 不与 3-点相邻。则()164402ch v=。如果()23nv，那么()116433026ch v =。当()7d v=时，根据引理 1(A6)，有()25nv。则()117452026ch v。傅水苗 DOI:10.12677/aam.2023.128351 3534 应用数学进展 当()8d v 时，()()()()1144022ch vd vd vd v=。下面将检验对于所有的()fF G，()0chf。情况情况 1：()4d f。当()3d f=时，如果 5-面与$f$相邻 s，那么根据 R1，有()134202chf+=。否则有()134302chf+。当()4d f=时，有()()0chfch f=。情况情况 2：()5d f=。在这种情况下，()541ch f=。根据引理 1(A1)，有()22nf。如果()22nf=，根据 R2，那么()11202chf=。如果()21nf=，那么()32nf。如果有两个 3-点，根据 R2，R3 和 R4，那么()1112042chf=。如果至多一个3-点，根据R2，R3和R4，那么()111032chf。如果()20nf=，那么()33nf。根据 R2，R3 和 R4，()11303chf =。情况情况 3：()6d f。为了估计 f 总的转权，我们将 f 的转权均匀地分配给 f 的边界中最接近转权接受者的边中的相关联的小于等于的 3 个顶点和相邻的 3 个面。已知通过 R2 一个 2-点最多从 f 得到权重 1，通过 R3 和 R4 一个 3-点最多从 f 得到权重12，f 最多给每个相邻的 3-面转权12。很容易看出，来自 f 的每个权中的接收者都恰好属于以下三种类型的一条路径 P，其中指数取模()d f：i)12iiiv vv+，其中()3id v，()13id v+，()23id v+，并且1iv+是非三角形的；ii)3iivv+，其中1iv+和2iv+是非三角形的，()3id v，()()123iid vd v+=，()33id v+；iii)极大序列ii kvv+由三角形边组成，其中1k，由（非三角形）边1iv v或1i ki kvv+扩张当且仅当()3id v=或者()3i kd v+=。设 P 由 l(P)条边组成，并通过 R1R3 导致 f 的总转权 m(P)。如果 P 是类型 iii)，则()()2m Pl P=，这意味着 P 的每条边在平均后从 f 中转权12得到。如果 P 的类型是 ii)，那么()3l P=并且()23m P=，所以 P 的每条边平均从 f 中最多得到29。假设 P 的类型是 i)；然后是()2l P=并且()1m P；所以 P 的每条边从 f 中最多得到12。此外，当且仅当()12id v+=并且()1id v+与 4-面相关联时，()1m P=。否则，()13m P=，所以 P 的两条边从 f 中得到16。由于我们的反例 G 的结构性质 A1A7，f 的边界中的每条边最多属于一条 i)iii)类型的路径。如 果()6d f=，那 么 根 据 定 理 1 的 假 设，具 有()1m P=的 路 径 P 是 不 可 能 的，所 以()164603chf=。如果()7d f=，那么 f 具有()1m P=的路径 P 最多有 3 条。当()1m P=的路径 P 最多有 2 条时，傅水苗 DOI:10.12677/aam.2023.128351 3535 应用数学进展 ()()1174474023chf=。当()1m P=的路径 P 有 3 条时，()174602chf=。如果()89d f，那么()()()1402chfd fd f。如果()10d f，那么我们记类型(i)的路径的总边数为()a P，类型(ii)的路径的总边数为()b P，类型iii)的路径的总边数为()c P。则我们有()()()()a Pb Pc Pd f+。所以()()()()()()()()()()()()121429211242291542181420chfdfa Pb Pc Pdfdfb Pb Pdfb Pdf+=+定理 1 证毕。3.总结与展望总结与展望 本文采用定理证明与权转移相结合的方法证明定理。权转移方法是图的染色理论中常用的证明方法之一，权转移方法经常结合其他方法和技术，如组合数学中的一些组合方法，在证明很多与染色问题有关的命题时，应用非常广泛，方法非常巧妙。当然该方法也有局限性，对于权转移的讨论过程比较繁琐。本文对于平面图是无圈 5-可选的猜想更进了一步，允许了 4-圈存在，图类更加广泛。在今后的研究中将会继续专研平面图是无圈 5-可选的猜想，证明方法进一步改进，减少繁琐的过程，尽量精简过程。参考文献参考文献 1 Grnbaum,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 Melnikov,L.S.(1976)Note to the Paper of Grnbaum on Acyclic Colorings.Discrete Mathe-matics,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 Choosability 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.Dis-crete 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.傅水苗 DOI:10.12677/aam.2023.128351 3536 应用数学进展 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 Acyclically 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