不含短圈平面图的2-距离列表染色.pdf

第 46 卷第 4 期浙江师范大学学报(自然科学版)Vol.46,No.42023 年 11 月 Journal of Zhejiang Normal University(Nat.Sci.)Nov.2023 DOI:10.16218/j.issn.1001-5051.2023.04.002不含短圈平面图的 2-距离列表染色俞家浩,陈 敏(浙江师范大学 数学科学学院,浙江 金华 321004)摘 要:图的染色理论在图论中有着重要的地位.主要运用权转移技巧,通过结构分析,研究了不含 4-圈和 5-圈的平面图的 2-距离列表染色.降低了这类平面图的 2-距离(+4)-列表染色的最大度下界,证明了不含 4-圈和 5-圈且 12 的平面图是 2-距离(+4)-列表可染的.关键词:平面图;2-距离染色;2-距离列表染色;圈;权转移中图分类号:O157.5 文献标识码:A 文章编号:1001-5051(2023)04-0368-11List 2-distance coloring of planar graphs without short cyclesYU Jiahao,CHEN Min(School of Mathematical Sciences,Zhejiang Normal University,Jinhua 321004,China)Abstract:Coloring theory of graphs had played an important role in graph theory.By using the discharging method and structure analysis,a result of list 2-distance coloring for a kind of planar graphs was improved.It was proved that every planar graph with 12 and without 4-cycles or 5-cycles could be 2-distance(+4)-list colorable.Key words:planar graph;2-distance coloring;list 2-distance coloring;cycle;discharging method0 引 言本文仅考虑有限简单无向图.令 G 是一个图,若 G 能被嵌入平面中,使得任意 2 条边仅在端点处相交,则称 G 是可平面图;称长度为 k 的圈为 k-圈;称 G 中最短圈的长度为 G 的围长,记作 g(G).图 G 的一个 2-距离 k-染色是指存在一个映射:V(G)1,2,k,使得 G 中任意距离不超过 2的顶点 u 和 v 都满足(u)(v);若 G 有一个 2-距离 k-染色,则称 G 是 2-距离 k-可染的;图 G 的 2-距离色数通常用2(G)表示,定义为使得 G 有 2-距离 k-染色的最小正整数 k 的值.图 G 的 2-距离染色的概念最早由 Wegner1于 1977 年引入并研究,他证明了每个 3 的平面图是2-距离 8-可染的,并提出以下猜想:猜想 11 令图 G 是最大度为 的平面图,则收文日期:2023-05-15;修订日期:2023-06-05基金项目:浙江省自然科学基金重点资助项目(LZ23A010004);国家自然科学基金资助项目(11971437)作者简介:俞家浩(1997),男,浙江绍兴人,硕士研究生.研究方向:组合数学与图论.通信作者:陈 敏.E-mail:chenmin 2(G)7,3;+5,4 7;32+1,8.围绕猜想 1,许多学者开展了研究.当 3 时,Thomassen2证明猜想 1 成立,即:每个满足 3 的平面图是 2-距离 7-可染的.对于一般平面图 G,van de Heuval 等3证明了2(G)2+25;随后,Molloy等4将上界改进为53+78.外平面图,作为一类特殊的平面图,Wang 等5证明了每个满足 7 的外平面图是 2-距离(+1)-可染的;Zhu 等6得到了每个满足 5 的平面图是 2-距离 20-可染的,以及每个满足 6 的平面图是 2-距离(5-7)-可染的结论;后来,Chen 等7对 5 平面图的 2-距离色数进行了一些改进,把上界 20 降到 19;Zhu 等8还证明了每个满足 78 的平面图是 2-距离(5-9)-可染的.2001 年,Kostochka 等9首次研究了图的 2-距离列表染色.给定图 G 一个颜色列表 L=L(v)vV(G),若 G 有一个2-距离染色,使得对于任意点 vV(G)均有(v)L(v),则称 G 是2-距离 L-可染的.若对于任意满足 L(v)k 的列表 L,其中 vV(G),G 都是 2-距离 L-可染的,则称 G 是 2-距离 k-列表可染的.图 G 的 2-距离列表色数,是使得 G 是 2-距离 k-列表可染的最小正整数 k 的值,记作l2(G).2007 年,Havet 等10证明:每个平面图是 2-距离32+o(1)()()-列表可染的.之后,不少学者研究了围长限制条件下平面图的 2-距离列表染色问题.Borodin 等11证明了每个 g6 且 24 的平面图是2-距离(+2)-列表可染的;Bonamy 等12将其改进为每个 g6 且 17 的平面图是 2-距离(+2)-列表可染的.人们将目光转向不含 4-圈和 5-圈的平面图类.为了方便,记 P4,5为不含 4-圈和 5-圈的平面图类.Cranston 等13证明了每个满足 32 的平面图 GP4,5是 2-距离(+3)-列表可染的;后来,Zhu等14加强为每个满足 26 的平面图 GP4,5是 2-距离(+3)-列表可染的;商春慧15证明了每个满足 13 的平面图 GP4,5是 2-距离(+4)-列表可染的.令 为一个正整数,P4,5表示所有满足最大度不超过 且无 4-圈和 5-圈的平面图类.本文主要证明了定理 1,改进了文献15中的结论.定理 1 如果 12 且 GP4,5,那么l2(G)+4.1 符号说明接下来介绍一些文中常用的符号标记.令 G=(V(G),E(G),F(G)为一个平面嵌入,其中 V(G),E(G)和 F(G)分别表示 G 的顶点集、边集和面集.对于 vV(G),用 dG(v)表示 v 在 G 中的度数,即与 v 关联的边数,简记为 d(v).若 d(v)=k(d(v)k 或 d(v)k),则称 v 为 G 的 k-点(k+-点或 k-点).用 Vk(G)表示 G 中所有 k-点组成的集合,简记为Vk;令 N(v)表示 v 的邻域;令 Nv=N(v)v表示 v 的闭邻域;v 的一个 k-邻点是指 N(v)中度数为 k的点.对于 fF(G),边界上边的条数(割边算 2 次)定义为 f 在 G 中的度数,通常用 dG(f)表示,一般简记为 d(f).若 f 上的顶点按某一方向排序为 v1,v2,vn,则记 f=v1v2vn.如果 2 个面(圈)至少共用1 个顶点,那么称它们是相交的.为了简便,一般用 nk(v)表示 v 的 k-邻点个数,用 mk(v)表示与 v 关联的 k-面个数,类似的定义可以运用在面上.关于本文图中的点,若该点的度数已经确定,则用实心点表示,否则用空心点表示.2 定理 1 的证明假设定理 1 不成立,令平面图 GP4,5是所有满足定理 1 的条件且 3+-点个数最少,或者在 3+-点个963 第 4 期 俞家浩,等:不含短圈平面图的 2-距离列表染色数相同的情况下,点数和边数之和最小的反例.记 f()=+4.令 L 为 G 的一个颜色列表配置,使得对于G 中每个点 v,都有 L(v)f().显然,G 是连通的.下面先讨论 G 的结构性质,然后运用欧拉公式及权转移技巧得到矛盾,从而完成定理 1 的证明.2.1 结构性质为了方便,令 F(v)和 A(v)分别表示在染色 中 v 的禁用色集和可用色集.不难推断,A(v)=L(v)F(v).引理 1(G)2.证明 反设存在 1-点 vV(G).令 G=G-v,则 GP4,5.由 G 的极小性知,G有一个 2-距离 L-染色.显然,F(v).这意味着 A(v)(+4)-=4.因此,很容易给 v 染上一种属于 A(v)的颜色,从而得到 G 的一个 2-距离 L-染色,矛盾.引理 1 证毕.引理 2 假设 vV2且 N(v)=v1,v2,则1)n2(v)=0.2)若 m3(v)=1,则 d(v1)+d(v2)+6.证明 1)反设 n2(v)1.根据对称性,不妨设 d(v1)=2.令 G=G-vv1,则 GP4,5.由极小性知,G有一个 2-距离 L-染色.抹去 v 与 v1的颜色,此时 F(v)+1 及 F(v1)+1.那么,A(v)(+4)-(+1)=3 且 A(v1)(+4)-(+1)=3.因此,很容易从 A(v)和 A(v1)中找到 2 种不同的颜色分别给 v 和 v1 染好色,从而获得 G 的一个 2-距离 L-染色,矛盾.2)反设 d(v1)+d(v2)+5.令 G=G-v,则 GP4,5.根据 G 的极小性,G有一个 2-距离 L-染色.此时,F(v)d(v1)+(d(v2)-2)+3,因此 A(v)(+4)-(+3)=1.那么,存在一种属于A(v)的颜色,将其染给 v,使得 G 是 2-距离 L-可染的,矛盾.引理 2 证毕.引理 3 假设 vV3且 N(v)=v1,v2,v3,则1)若 d(v1)=2,则 d(v2)+d(v3)+3.特别地,当 v2v3E(G)时,d(v2)+d(v3)+5.2)若 3d(v1)10 且 v2v3E(G),则 d(v1)+d(v2)+d(v3)+6.证明 1)反设 d(v2)+d(v3)+2.令 G=G-vv1,则 GP4,5.由 G 的极小性知,G有一个 2-距离 L-染色.抹去 v 与 v1的颜色,此时 F(v)(d(v1)-1)+d(v2)+d(v3)=1+d(v2)+d(v3)+3 且F(v1)+2,这表明 A(v)1 且 A(v1)2.因此,可依次给 v 和 v1染上 2 种不同的颜色,使得G 有一个 2-距离 L-染色,矛盾.下面假设 v2v3E(G)且 d(v2)+d(v3)+4.同样地,令 G=G-vv1,则 GP4,5.由 G 的极小性知,G有一个 2-距离 L-染色.类似地,抹去 v 与 v1的颜色,易知 F(v)(d(v1)-1)+(d(v2)-1)+(d(v3)-1)=d(v2)+d(v3)-1+3 且 F(v1)+2.那么,A(v)1 且 A(v1)2.因此,很容易找到 2 种不同的颜色依次给 v 和 v1染好色,使得 G 是 2-距离 L-可染的,矛盾.2)反设 d(v1)+d(v2)+d(v3)+5.令 G=G-v-v2v3+v1,2+v1,3+v2,3+v1,2v1+v1,2v2+v1,3v1+v1,3v3+v2,3v2+v2,3v3,其中 v1,2,v1,3和 v2,3是新添加的 3 个 2-点.不难验证,此时 G既不含 4-圈也不含 5-圈,而且 G的最大度依然不超过.换言之,GP4,5.另外,V3+(G)0.n2(v)=4.不妨假设 d(v1)=d(v2)=d(v3)=d(v4)=2.类似地,引理 2 的 2)蕴含了 m3(v)=0 的结论.对于每个 i1,2,3,4,记 vi为 vi除 v 之外的邻点.若 d(v5)4,则由 R1.2b 知,f4和 f5给 v 各转权16.因此,(v)1-134+162=0.否则,考虑 d(v5)=3.此时根据引理 5 的 2),易得 d(vi)=,其中i=1,2,3,4.所以,根据 R5.1,每个 vi给 v 转权16,从而有(v)1-134+164=130.n2(v)=3.根据对称性,不妨设 d(v1)=d(v2)=d(vi)=2,其中 i3,4.记 vj为 vj除 v 之外的邻点,其中 j=1,2,i.同样地,引理 2 的 2)确保了 m3(v)1 的结论,而且,m3(v)=1 当且仅当 i=3.下面根573 第 4 期 俞家浩,等:不含短圈平面图的 2-距离列表染色据 m3(v)的值进行讨论.i)m3(v)=0.显然,(v)1-133=0.ii)m3(v)=1.此时,i=3 且 d(f4)=3,即 v4v5E(G).不妨设 d(v4)d(v5).下面的讨论围绕 d(v4)的值展开.a)d(v4)4,则(v4,v5)=(4+,4+).由 R2R4 得到,v 不给 4+-点转权.因此,(v)1-133=0.b)d(v4)=3.记 v4为 v4除 v 和 v5之外的邻点.显然,根据引理 1,有 d(v4)2.若 d(v4)=2,则由引理 5 的 3)知,每个 vi的度数至少为-1.而且,由引理 3 的 1)知,d(v5)=.根据 R3.2a,R5.1,R6.2,(v)1-133-23+163+13=160.否则,假设 d(v4)3.此时,v 无需给 v4转权.因此,(v)1-133=0.n2(v)=2.不妨设 d(v1)=d(vi)=2,其中 i2,3.再一次,根据 G 中无 4-圈的假设和引理 2 的2)可推断,m3(v)1.而且,m3(v)=1 当且仅当 i=2.下面根据 m3(v)展开讨论.i)m3(v)=0.显然,(v)1-132=130.ii)m3(v)=1.此时 i=2.根据对称性,不妨设 d(f3)=3,那么,v3v4E(G).进一步,不妨设 d(v3)d(v4).下面围绕 d(v3)的值进行讨论.a)d(v3)4.则(v3,v4)=(4+,4+).同样地,除了 v1和 v2,此时 v 无需给其他邻点转权.因此,(v)1-132=130.b)d(v3)=3.记 v3为 v3除 v 和 v4之外的邻点.倘若 d(v3)=2,则由引理 3 的 1)知,d(v4)=.再根据 R3.2a,有(vv3)=23.因此,根据 R6.2,(v)1-132-23+13=0.否则,考虑 d(v3)3.不难推出(v)1-132=130.n2(v)1.鉴于 G 不包含 4-圈,显然有 m3(v)2.为了计算方便,先估算一下 v 转出的权值.不妨设 d(vi)3.由规则 R3 知,v 只在1 种情况下转权给 vi,即(vvi)=23当且仅当 d(vi)=3 且 vvi关联3-面,不妨设 fi=vvivi+1为 3-面.进一步,此时,由 R3.2a 知,vi还要相邻 1 个不在 fi上的 2-点.再根据引理 3 的 1),很容易推出 d(vi+1)=.因此,根据 R6.2,(vi+1v)=13.结合 3-面不能相邻的事实,很容易推出(v)1-13n2(v)-13m3(v)=1-13(n2(v)+m3(v)1-133=0.5)6d(v)-2.同样地,为了便于计算,先估算一下 v 转给邻点 vi的权值.vvi不关联 3-面.当 d(vi)=2 时,根据 R2.1,(vvi)=13;当 d(vi)=3 时,根据 R3.1,(vvi)=13;当 d(vi)=4 时,根据 R4.1,(vvi)=13;当 d(vi)5 时,v 无需转权给 vi.因此,v 转给每个非 3-面邻点的权至多为13.vvi关联 3-面.不妨设 fi=vvivi+1为3-面且 d(vi)d(vi+1).当 d(vi)=3 时,根据 R3.2a,R3.2b 和673浙江师范大学学报(自然科学版)第 46 卷R3.2c,(vvi)23;当 d(vi)=4 时,根据 R4.2a 和 R4.2b,(vvi)23;当 d(vi)5 时,v 无需转权给 vi.现在假设 d(vi)=2.由引理 2 的 2)知,d(vi+1)+6-d(v).i)当 d(v)=6 时,有 d(vi+1)=.由 R2.2 和 R6.2 知,(vvi)=1 且(vi+1v)=13.因此,v 实际转出的权为23.ii)当 d(v)=7 时,有 d(vi+1)-1.由 R2.2 和 R6 知,(vvi)=1 且(vi+1v)19.因此,v 实际转出的权至多为89.iii)当 8d(v)-2 时,由 R2.2 知,(vvi)=1.根据以上讨论,可以得到如下结论:当 d(v)=6 时,(v)2-23m3(v)-13(6-2m3(v)=0;当 d(v)=7 时,(v)3-89m3(v)-13(7-2m3(v)=23-29m3(v)23-293=0;当 8d(v)-2 时,(v)d(v)-4-m3(v)-13(d(v)-2m3(v)=23d(v)-4-13m3(v)23d(v)-4-16d(v)=12d(v)-40.6)-1d(v).类似地,先估算一下 v 转给邻点 vi的权值.vvi不关联 3-面.当 d(vi)=3 时,根据 R3.1,(vvi)=13;当 d(vi)=4 时,根据 R4.1,(vvi)=13;当 5d(vi)7 时,根据 R6,(vvi)13.现在假设 d(vi)=2.记 vi为 vi的另外 1 个邻点.i)当 d(v)=-1 时,根据 R2.1 和 R5.1,(vvi)+(vvi)13+16=12.ii)当 d(v)=时,根据 R2.1 和 R5.2,(vvi)+(vvi)13+13=23.vvi关联 3-面.不妨设 fi=vvivi+1为 3-面且 d(vi)d(vi+1).i)假设 d(v)=-1.当 d(vi)=3 时,根据 R3.2a,R3.2b,R3.2c 和 R4.2a,(vvi)+(vvi+1)23+13=1;当 d(vi)=4 时,根据 R4.2a,R4.2b 和 R6.1,(vvi)+(vvi+1)23+19=79;当 d(vi)5 时,根据 R6.1,(vvi)+(vvi+1)192=29.下面假设 d(vi)=2.由引理 2 的 2)知,d(vi+1)+6-(-1)=7.根据 R2.2 和 R6.1,(vvi)+(vvi+1)1+19=109.因此,当 d(v)=-1 时,v 实际转出的权至多为109.ii)假设 d(v)=.当 d(vi)3,4时,根据 R3.2,R4.2b 和 R6.2,(vvi)+(vvi+1)23+23=43;当 d(vi)5 时,根据 R5.1 和 R6.2,(vvi)+(vvi+1)13+13=23.现在考虑 d(vi)=2.由引理 2773 第 4 期 俞家浩,等:不含短圈平面图的 2-距离列表染色的 2)知,d(vi+1)+6-=6.根据 R2.2 和 R6.2,(vvi)+(vvi+1)1+13=43.因此,当 d(v)=时,v 实际转出的权至多为43.根据以上讨论,得到如下结论:当 d(v)=-1 时,(v)d(v)-4-109m3(v)-12(d(v)-2m3(v)=12d(v)-4-19m3(v)12d(v)-4-118d(v)=49d(v)-4=49(-1)-4449-4=890;当 d(v)=时,(v)d(v)-4-43m3(v)-23(d(v)-2m3(v)=13d(v)-4=13-40.断言 2 证毕.根据断言 1 和断言 2 得到,任意 xV(G)F(G)满足(x)0,因此,极小反例 G 不存在,从而定理 1 成立.3 结 语一直以来,关于不含 4-圈和 5-圈平面图的 2-距离列表染色是热门的研究课题.作为文章的结尾,提出以下问题:问题 1 是否存在正整数 k26,使得不含 4-圈和 5-圈且 k 的平面图 G 有l2(G)+3?参考文献:1WEGNER G.Graphs with given diameter and a coloring problemR.Dortmund:University of Dortmund,1977.2THOMASSEN C.The square of a planar cubic graph is 7-colorableJ.J Combin Theory Ser B,2018,128:192-218.3VAN DE HEUVAL J,MCGUINNESS S.Coloring of the square of a planar graphJ.J Graph Theory,2003,42(2):110-124.4MOLLOY M,SALAVATIPOUR M R.A bound on the chromatic number of square of a planar graphJ.J Combin Theory Ser B,2005,94(2):189-213.5WANG W F,LIH K W.Note on coloring the square of an outerplanar graphJ.Ars Combin,2008,86:89-95.6ZHU J L,BU Y H.Minimum 2-distance coloring of planar graphs and channel aassignmentJ.J Comb Optim,2018,36(1):55-64.7CHEN M,MIAO L Y,ZHOU S.2-distance coloring of planar graphs with maximum degree 5J.Discrete Math,2022,345(4):112766.8ZHU J L,BU Y H,ZHU H G.Wegners conjecture on 2-distance coloring for planar graphsJ.Theoret Comput Sci,2022,926:71-74.9KOSTOCHKA A V,WOODALL D R.Choosability conjectures and multicircuitsJ.Discrete Math,2001,240(1/2/3):123-143.10HAVET F,VAN DE HEUVEL J,MCDIARMID C,et al.List colouring squares of planar graphsJ.Electron Note Discrete Math,2007,29:515-519.11BORODIN O V,IVANOVA A O.List 2-distance(+2)-coloring of planar graphs with girth six and 24J.Sibirsk Mat Zh,2009,50(6):1216-1224.12BONAMY M,LVQUE B,PINLOU A.Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance(+2)-colorableJ.Discrete Math,2014,317:19-32.13CRANSTON D W,JAEGER B.List-coloring the squares of planar graphs without 4-cycles and 5-cyclesJ.J Graph Theory,2017,85(4):721-737.14ZHU H Y,GU Y,SHENG J J,et al.List 2-distance+3-coloring of planar graphs without 4,5-cyclesJ.J Comb Optim,2018,36(4):1411-1424.15商春慧.平面图的 2-距离染色D.金华:浙江师范大学,2016.(责任编辑 陶立方)873浙江师范大学学报(自然科学版)第 46 卷