稀疏图的r-动态染色.pdf

第 47 卷第 2 期浙江师范大学学报(自然科学版)Vol.47,No.22024 年 5 月 Journal of Zhejiang Normal University(Nat.Sci.)May 2024 DOI:10.16218/j.issn.1001-5051.2024.015稀疏图的 r-动态染色卜月华1,2,王晓燕1,朱洪国1(1.浙江师范大学 数学科学学院,浙江 金华 321004;2.浙江广厦建设职业技术大学 基础部,浙江 东阳 322100)摘 要:通过分析极小反例的结构性质,运用权转移的方法,研究了对于 mad(G)145 的稀疏图 G 的 r-动态染色数,证明了对于满足 mad(G)145的图 G,若 r9,则r(G)r+2.研究结果推广了稀疏图 r-动态染色的已知结果.关键词:稀疏图;r-动态染色;最大平均度;权转移中图分类号:O157.5 文献标识码:A 文章编号:1001-5051(2024)02-0150-07On the r-dynamic coloring of sparse graphsBU Yuehua1,2,WANG Xiaoyan1,ZHU Hongguo1(1.School of Mathematical Sciences,Zhejiang Normal University,Jinhua 321004,China;2.Department of Basics,Zhejiang Guangsha Vocational and Technical University of Construction,Dongyang 322100,China)Abstract:It was studied the r-dynamic chromatic number of sparse graph G with mad(G)14/5 by analyzing the structural properties of the minimal counterexample and applying the discharging method.It was proved that r(G)r+2 if G was a given graph with mad(G)14/5 and r9.The presented result generalized the known results of the r-dynamic chromatic number of sparse graphs.Key words:sparse graph;r-dynamic coloring;maximum average degree;discharging0 引 言本文考虑的均是简单有限图.图 G 的顶点集、边集、最大度、围长分别用 V(G),E(G),(G),g(G)表示;顶点 v 在图 G 中的度、邻点集分别用 dG(v),NG(v)表示,在不引起混淆的情况下,一般分别简写为d(v),N(v);图 G 的最大平均度 mad(G)是指图 G 的所有非空子图的平均度的最大值,即 mad(G)=收文日期:2023-04-10;修订日期:2023-05-12基金项目:国家自然科学基金资助项目(12031018;12201569)作者简介:卜月华(1960),男,浙江东阳人,教授,博士生导师.研究方向:组合数学与图论.通信作者:朱洪国.E-mail:zhuhongguo max2 E(H)V(H)HG.文中其余未定义的术语和符号参考文献1.对于正整数 k 和 r,图 G 存在一个正常的(k,r)-动态染色,是指存在映射:V(G)1,2,k,满足以下 2 个条件:1)对于任意的边 uvE(G),有(u)(v);2)对于任意的顶点 vV(G),有(NG(v)mindG(v),r.给定一个正整数 r,则称r(G)=mink 图 G 存在一个正常的(k,r)-动态染色为图 G 的 r-动态染色数.对于图 G 的每个顶点 v,给定一个可用色集 L(v),且 L(v)k,则称 L=L(v):vV(G)为图 G的一个 k-列表配置.若对于任意的 k-列表配置 L,存在图 G 的一个(k,r)-态染色,使得对于任意的点vV(G),有(v)L(v),则称图 G 是列表(k,r)-动态可染的.称 chr(G)=mink 图 G 是列表(k,r)-动态染色的为图 G 的列表 r-动态染色数.显然,有 chr(G)r(G).图的动态染色是由 Montgomery2在 2001 年首次提出的.Chen 等3证明了对于平面图 G,有2(G)5.Song 等4证明了对于不含 K4-minor 的图 G,若 2 r 3,则r(G)r+3;若 r 4,则r(G)3r2+1;并依据 Wegner 猜想提出了 r-动态染色数猜想.猜想 1设图 G 是平面图,若 1 r 2,则r(G)r+3;若 3 r 7,则r(G)r+5;若 r 8,则r(G)3r2+1.对于任意的平面图 G,Loeb 等5证明了 ch3(G)10;Song 等6证明了若 r8,则r(G)2r+16.对于任意的简单图 G,Cheng 等7证明了若 mad(G)73,则3(G)5;Kim 等8证明了若 mad(G)187145,6(),则 ch3(G)6(7,8);Zhu 等9证明了对于 mad(G)18752,125()的图 G,若 r8(6,5),则chr(G)r+1.对于 g(G)7 的平面图 G,Yi 等10证明了若 r16,则r(G)r+1.对于 g(G)8 的平面图 G,La 等11证明了若 r9,则r(G)r+1.本文将证明下面的定理:定理 1 设图 G 满足 mad(G)145,若 r9,则r(G)r+2.最大平均度 mad(G)通常用于衡量图 G 的稀疏度,与此同时,还可以通过围长 g(G)衡量图 G 的稀疏度.若图 G 是平面图,则最大平均度 mad(G)和围长 g(G)满足以下关系:命题 1 任意的平面图 G,满足(mad(G)-2)(g(G)-2)4.因此,对于平面图 G,还能得到下面的推论:推论 1 设平面图 G 满足 g(G)7,若 r9,则r(G)r+2.1 记 号对于顶点 v,若 d(v)=k(或 d(v)k,或 d(v)k),则称 v 为 k-点(或 k+-点,或 k-点).对于图 G 中的 k-点 v,记邻点集 N(v)=v1,v2,vk,且 d(v1)d(v2)d(vk).考虑 2-点 vi,记邻点集 N(vi)=v,vi1.用 ni(v)表示 N(v)中 i-点的个数.k(i)-点表示与 i 个 2-点相邻的 k-点.k(i-)-点表示至多与 i 个2-点相邻的 k-点.若顶点 v 和 w 有一个公共邻点 u,且 d(u)=2,则称 v 和 w 弱相邻.对于不交路 v0v1vkvk+1,若 d(v0)3,d(v1)=d(v2)=d(vk)=2,d(vk+1)3,则称 v0v1vkvk+1为 k-路.当 kj 时,k-路151 第 2 期 卜月华,等:稀疏图的 r-动态染色也称为 j+-路.对于不交路 v0v1v2v3v4,若 d(v0)3,d(v1)=d(v3)=2,v2为 3(3)-点,d(v4)3,则称v0v1v2v3v4为 3(3)-路.2-路和 3(3)-路分别简写为 P(2)和 P(3).设 H 为 G 的子图,构造图 GH:GH的顶点集 VH为 G 中所有 H-子图上的顶点,GH的边集 EH为 G 中所有 H-子图上的边.称由 VH和 EH构成的图 GH为 G 的 H-导出图.对于 VV,GV是图 G 在 V上的导出子图,若存在映射:Vk是 GV上的一个(k,r)-动态染色,则称 是 G 关于 GV的部分(k,r)-动态染色.当 是 G 关于 GV的部分(k,r)-动态染色时,对于 vV-V,定义(v)=.对于任意的 vV(G),定义以下颜色集 v:v=(v),(NG(v)r;(v)(NG(v),(NG(v)r.由 v的定义可知,v r.令 F(v)=uNG(v)u表示为 v 的禁用色集.对于 vV(G),若满足F(v)k,则称 v 是可以被染好的.2 定理 1 的证明本文利用极小反例和权转移的方法证明定理 1.设 G 是定理 1 中满足 V(G)+E(G)最小的一个反例,即图 G 满足 mad(G)145,r9,r(G)r+3,但对于图 G 中的任意一个真子图 G,有r(G)r+2.为了方便表述,记 k=r+2.接下来研究图 G 的一些结构性质.引理 1 图 G 是连通的且不含 1-点.证明 若图 G 不是连通的,则由图 G 的极小性知,图 G 的每一连通分支都是(k,r)-动态可染的,因此,图 G 是(k,r)-动态可染的,矛盾.若图 G 存在 1-点 v,且 uvE(G),则由图 G 的极小性知,G-uv 存在一个(k,r)-动态染色.抹去 v的颜色,因为 F(v)u rk,所以 v 可以重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.引理 1 证毕.引理 2 对于图 G,满足以下结构:1)图 G 不含 3+-路;2)图 G 中 2-路的 2 个端点皆为 r-点.证明 1)若图 G 存在 3+-路 v0v1v2vkvk+1,其中 d(v1)=d(v2)=d(vk)=2,k3,则由图 G 的极小性知,G-v1v2存在一个(k,r)-动态染色.抹去 v1和 v2的颜色,因为 F(v1)v0(v3)r+1,F(v2)(v0),(v3),(v4)3,所以 v1,v2可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.2)设 v0v1v2v3为图 G 中的 2-路,其中 d(v1)=d(v2)=2.若存在 d(v0)r-1,则由图 G 的极小性知,G-v1v2存在一个(k,r)-动态染色.抹去 v1和 v2的颜色,因为 F(v2)v3(v0)r+1,F(v1)v0(v3)r-1+1=r,所以 v2和 v1可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.若存在 d(v0)r+1,则由图 G 的极小性知,G-v1存在一个(k,r)-动态染色.抹去 v2的颜色,因为v0=1,所以 F(v2)v3(v0)r+1,F(v1)v0(v3)1+1=2.因此,v2和 v1可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.引理 2 证毕.引理 3 G 的 2-路 P(2)-导出图 GP(2)无圈.证明 若 GP(2)有圈,则图 G 中存在圈 u0 x0y0u1x1y1u2ul-1xl-1yl-1u0.其中,d(xj)=d(yj)=2.由引理251浙江师范大学学报(自然科学版)第 47 卷2 的2)知,d(uj)=r(0jl-1).由图 G 的极小性知,G-x0y0存在一个(k,r)-动态染色.抹去所有 xj和yj的 颜 色(0 j l-1),因 为F(xj)uj(uj+1)r-2+1+1=r,F(yj)uj+1(uj)r-2+1+1=r,所以所有的 xj和 yj至少有 2 种颜色可染(0jl-1).由偶圈的 2-可选择性知,所有的 xj和 yj(0jl-1)均可以重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.引理 3证毕.引理 4 设 v 为图 G 的 3-点,N(v)=v1,v2,v3.1)若 d(vi)=2,N(vi)=v,vi1,则 d(vi1)=r(i=1,2,3);2)若 d(vi)=2,N(vi)=v,vi1,且 3d(v3)7,则 d(vi1)r-1(i=1,2);3)若 d(v1)=2,N(v1)=v,v11,且 d(v2)+d(v3)r,则 d(v11)r-1;4)3(2)-点与 3(2)-点及 4(3)-点不相邻;5)若存在 3-点 u 与 3(2)-点 v 相邻时,其中 N(u)=v,u1,u2,则 d(u1)+d(u2)r.证明 1)若存在 d(v11)r-1,则由图 G 的极小性知,G-vv1存在一个(k,r)-动态染色.抹去 v 和v1的 颜 色,因 为F(v1)v11(v2),(v3)r-1+2=r+1,F(v)(v2),(v21),(v3),(v31),(v11)5,所以 v1和 v 可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.若存在d(v11)r+1,则由图G 的极小性知,G-v1存在一个(k,r)-动态染色.抹去v 的颜色,因为 v11=1,所以 F(v)(v2),(v21),(v3),(v31),(v11)5,F(v1)v11(v2),(v3)1+2=3,因此,v 和v1可以依次重新染好,得到图G 的一个(k,r)-动态染色,矛盾.2)若存在 d(v11)r-2,则由图 G 的极小性知,G-vv1存在一个(k,r)-动态染色.抹去 v,v1和 v2的颜色,因为 F(v2)v21(v3)r+1,F(v)v3(v11),(v21)7+2=9,F(v1)v11(v3)r-2+1=r-1,所以 v2,v 和 v1可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.3)若存在 d(v11)r-2,则由图 G 的极小性知,G-vv1存在一个(k,r)-动态染色.抹去 v 和 v1的颜色,因为 F(v)v2v3(v11)r+1,F(v1)v11(v2),(v3)r-2+2=r,所以 v 和 v1可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.4)若存在3(2)-点v 和3(2)-点u 相邻,则由图G 的极小性知,G-uv 存在一个(k,r)-动态染色.抹去 u 和 v的颜色,因 F(u)u1u2(v1),(v2)6,F(v)v1v2(u1),(u2)6,故u 和v 可以依次重新染好,得到图G 的一个(k,r)-动态染色,矛盾.若存在 3(2)-点 v 和 4(3)-点 u 相邻,则由图 G 的极小性知,G-uv 存在一个(k,r)-动态染色.抹去u 和v的 颜 色,因 为F(u)u1u2u3(v1),(v2)8,F(v)v1v2(u1),(u2),(u3)7,所以 u 和 v 可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.5)若存在 d(u1)+d(u2)r-1,则由图 G 的极小性知,G-uv 存在一个(k,r)-动态染色.抹去 u 和 v的颜 色,因 为F(u)u1u2(v1),(v2)r-1+2=r+1,F(v)v1v2(u1),(u2)2+2+2=6,所以 u 和 v 可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.引理 4 证毕.引理 5 G 的 3(3)-路 P(3)-导出图 GP(3)无圈.证明 若 GP(3)有圈,则 G 中存在圈 u0 x0y0z0u1x1y1z1u2ul-1xl-1yl-1zl-1u0.其中,d(xj)=d(zj)=2,yj为 3(3)-点.记 N(yj)=xj,zj,wj,则由引理 4 的 1)知,d(uj)=r(0jl-1).由图 G 的极小性知,G-351 第 2 期 卜月华,等:稀疏图的 r-动态染色x0y0存在一个(k,r)-动态染色.抹去所有 xj,yj和 zj的颜色(0 j l-1),因为F(xj)uj(wj)r-2+1+1=r,F(zj)uj+1(wj)r-2+1+1=r,所以 xj和 zj至少有 2种颜色可染(0jl-1).由偶圈的 2-可选择性可知,所有的 xj和 zj均可以重新染好.随后,因为F(yj)xjzjwj 6,所以所有的 yj均可以重新染好(0jl-1),得到图 G 的一个(k,r)-动态染色,矛盾.引理 5 证毕.引理 6 设 v 为图 G 的 4-点,N(v)=v1,v2,v3,v4.若 d(vi)=2,N(vi)=v,vi1,则 d(vi1)r-1(i=1,2,3,4).证明 若存在 d(v11)r-2,则由图 G 的极小性知,G-vv1存在一个(k,r)-动态染色.抹去 v 和 v1的 颜 色,因 为F(v)(v11),(v2),(v21),(v3),(v31),(v4),(v41)7,F(v1)v11(v2),(v3),(v4)r-2+3=r+1,所以 v1和 v 可以依次重新染好,得到图 G 的一个(k,r)-动态染色,矛盾.引理 6 证毕.定义 1(2-路的赞助商)考虑图 G 的 2-路的导出图 GP(2).由引理 2 的 2)知,每条 2-路的 2 个端点都是 r-点,并由引理3 知,GP(2)是一个森林 F.对于森林 F 的子树,可以选择1 条2-路的1 个端点 r-点作为树的根节点,每条 2-路都能按照远离根节点的原则选择该 2-路的另一个端点 r-点与之一一对应,称相对应的 r-点为该 2-路的赞助商.显然,每条 2-路中的 2 个端点 r-点有且只有 1 个是该 2-路的赞助商,每条 2-路中的端点 r-点至多只为 1 条 2-路的赞助商.定义 2(3(3)-点的赞助商)考虑图 G 的 3(3)-路的导出图 GP(3).由引理 4 的 1)知,3(3)-点的 3个弱相邻点都是 r-点,因此,每条 3(3)-路的 2 个端点都是 r-点,并由引理 5 知,GP(3)是一个森林 F.对于森林 F 的子树,可以选择 1 条 3(3)-路的 1 个端点 r-点作为树的根节点,每条 3(3)-路都能按照远离根节点的原则选择该 3(3)-路的另一个端点 r-点与之一一对应,称相对应的 r-点为该 3(3)-路上的 3(3)-点的赞助商.显然,3(3)-点的 3 个弱相邻 r-点有且只有 2 个 r-点是该 3(3)-点的赞助商,每个 3(3)-点的弱相邻 r-点至多只为 1 个 3(3)-点的赞助商.因为图 G 满足 mad(G)145,所以一定有vV(G)(5d(v)-14)vV(G)(v)=vV(G)(v)0.该矛盾说明构造出的极小反例图 G 是不存在的,即定理 1 是成立的.为了表述方便,用(uv)表示 u给 v 转的权值,其中 u,vV(G).下面定义权转移规则:R1:对于 2-点 v,若 v 是 1-路中的 2-点且 uvE(G),则(uv)=2.否则,v 是 2-路 xuvy 中的 2-点.若 y 是该2-路 xuvy 的赞助商,则(yv)=4,(yu)=1;若 y 不是该2-路 xuvy 的赞助商,则(yv)=3.R2:对于 3(3)-点 v,设 w 与 v 弱相邻,若 w 是 3(3)-点 v 的赞助商,则(wv)=2;若 w 不是 3(3)-点 v 的赞助商,则(wv)=1.R3.1:对于 3(2)-点 v,uvE(G),若 d(u)8,则(uv)=3;若 3d(u)7,则(uv)=1.R3.2:对于 3(1-)-点 v,uvE(G),若 d(u)7,则(uv)=2;若 5d(u)6,则(uv)=1.R3.3:对于 3(2-)-点 v,设 w 与 v 弱相邻,若 d(w)r-1,则(wv)=1.451浙江师范大学学报(自然科学版)第 47 卷R4:对于 4-点 v,设 w 与 v 弱相邻,若 d(w)r-1,则(wv)=1.接下来证明对于任意的 vV(G),都有(v)0,进而完成对定理 1 的证明.1)当 d(v)=2 时,(v)=-4.由引理 2 的 1)知,图 G 中不存在 3+-路.若 v 是 1-路 uvw 中的 2-点,则由 R1 知,(uv)=2,(wv)=2,因此,(v)=-4+22=0.设 v 是 2-路 xuvy 中的 2-点,若 y 是该 2-路 xuvy 的赞助商,则由 R1 知,(yv)=4,因此,(v)=-4+4=0;若 y 不是该 2-路 xuvy 的赞助商,则由 2-路的赞助商的定义知,x 是该 2-路 xuvy 的赞助商.由 R1 知,(xv)=1,(yv)=3,因此,(v)=-4+1+3=0.2)当 d(v)=3 时,(v)=1.n2(v)=3.由引理 4 的 1)知,d(vi1)=r(i=1,2,3).又由 3(3)-点的赞助商的定义知,只有 2 个 r-点是 3(3)-点 v 的赞助商,不妨假设为 v11和 v21.由 R2 知,(v11v)=2,(v21v)=2,(v31v)=1,再由 R1 知,(v)=1-23+22+1=0.n2(v)=2.此时,v11,v21与 v 弱相邻.若 3d(v3)7,则由引理 4 知,d(vi1)r-1(i=1,2),且 v3不为 3(2)-点及 4(3)-点.由 R3.1 和 R3.3 知,(v3v)=1,(v11v)=1,(v21v)=1,再由 R1 知,(v)=1-22+1+12=0.若 d(v3)8,则由 R3.1 知,(v3v)=3,再由 R1 知,(v)1-22+3=0.n2(v)=1.若 v2为 3(2)-点,由引理 4 的 5)知,d(v1)+d(v3)r9,即 d(v3)7,则由 R3.1 和R3.2 知,(vv2)=1,(v3v)=2,再由 R1 知,(v)1-2-1+2=0.若 v 不与 3(2)-点相邻,且d(v2)+d(v3)r,则由引理 4 的 3)知,d(v11)r-1.由 R3.3 知,(v11v)=1,再由 R1 知,(v)1-2+1=0.若 d(v2)+d(v3)r+110,则 v3一定是 5+-点.由 R3.2 知,1(v3v)2,再由 R1 知,(v)1-2+1=0.n2(v)=0.由引理 4 的 5)知,v 至多与 2 个 3(2)-点相邻.若 v 至多与 1 个 3(2)-点相邻,则由R3.1知,(v)1-1=0;若 v 与 2 个 3(2)-点相邻,则由引理 4 的 5)知,d(v2)+d(v3)r9,即 d(v3)6.由R3.1 和 R3.2 知,(vvi)=1(i=1,2),1(v3v)2,再由 R1 知,(v)1-12+1=0.3)当 d(v)=4 时,(v)=6.若 n2(v)=4,vi1与 v 弱相邻(i=1,2,3,4),则由引理 6 知,d(vi1)r-1,由 R4 知,(vi1v)=1(i=1,2,3,4),再由 R1 知,(v)=6-24+14=20;若 n2(v)=3,则由引理 4 的 4)知,v 不与 3(2)-点相邻,由 R1 知,(v)6-23=0;若 n2(v)2,考虑最坏情况,则由 R1 和 R3.1 知,(v)6-2n2(v)-(4-n2(v)=2-n2(v)0.4)当 5d(v)7 时.考虑最坏情况,由 R1 和 R3 知,v 沿每条关联边转出的权至多为 2,因此,(v)5d(v)-14-2d(v)=3d(v)-1435-14=10.5)当 d(v)=8 时.考虑最坏情况,由 R1,R3 和 R4 知,v 沿每条关联边转出的权至多为 3,因此,(v)5d(v)-14-3d(v)=2d(v)-14=28-14=20.6)当 d(v)9 时.此时考虑 v 是否为 2-路的赞助商或者为 3(3)-点的赞助商.若 v 既不是 2-路的赞助商,也不是 3(3)-点的赞助商,则由 R1R4 知,v 沿每条关联边转出的权至多为 3,因此,(v)5d(v)-14-3d(v)=2d(v)-1429-14=40.若 v 是 2-路的赞助商,但不是 3(3)-点的赞助商,则 d(v)=r9.由 R1 知,v 沿该 2-路的边转出4+1=5 的权,由 R1R4 知,v 沿其余关联边转出的权至多为 3,因此,(v)5d(v)-14-5-3(d(v)-551 第 2 期 卜月华,等:稀疏图的 r-动态染色1)=2d(v)-16 29-16=20.若 v 不是 2-路的赞助商,但是 3(3)-点的赞助商,则 d(v)=r9.由 R1 和 R2 知,v 沿该 3(3)-点的边转出 2+2=4 的权,由 R1R4 知,v 沿其余关联边转出的权至多为 3,因此,(v)5d(v)-14-4-3(d(v)-1)=2d(v)-15 29-15=30.若 v 既是 2-路的赞助商,也是 3(3)-点的赞助商,则 d(v)=r9.由 R1 知,v 沿该 2-路的边转出4+1=5 的权,由 R1 和 R2 知,v 沿该 3(3)-点的边转出的权为 2+2=4,由 R1R4 知,v 沿其余关联边转出的权至多为 3,因此,(v)5d(v)-14-5-4-3(d(v)-2)=2d(v)-17 29-17=10.至此,对于任意的点 vV(G),有(v)0.综上所述,得到了以下有矛盾的式子:0 vV(G)(v)=vV(G)(v)0.以上的矛盾说明构造出的极小反例图 G 是不存在的,因此,定理 1 是成立的.定理 1 证毕.3 结 语本文通过分析极小反例的结构性质,并利用权转移方法,证明了对于满足最大平均度mad(G)145的稀疏图 G,若 r9,则r(G)r+2.结合文献9-10的结论,笔者提出以下问题:设图 G 满足最大平均度 mad(G)145,探究尽可能小的 c0,使得当 rc0时有r(G)r+1,这是个十分值得研究的问题.参考文献:1BONDY J A,MURTY U S R.Graph theoryM.Berlin:Springer,2008.2MONTGOMERY B.Dynamic coloring of graphsD.Morgantwon:West Virginia University,2001.3CHEN Y,FAN S H,LAI H J,et al.On dynamic coloring for planar graphs and graphs of higher genusJ.Discrete Appl Math,2012,160(7/8):1064-1071.4SONG H M,FAN S H,CHEN Y,et al.On r-hued coloring of K4-minor free graphsJ.Discrete Math,2014,315/316:47-52.5LOEB S,MATHONEY T,REINIGER B,et al.Dynamic coloring parameters for graphs with given genusJ.Discrete Appl Math,2018,235(1):129-141.6SONG H M,LAI H J.Upper bounds of r-hued colorings of planar graphsJ.Discrete Appl Math,2018,243:262-269.7CHENG J,LAI H J,LORENZEN K J,et al.r-hued coloring of sparse graphsJ.Discrete Appl Math,2018,237:75-81.8KIM S J,PARK B.List 3-dynamic coloring of graphs with small maximum average degreeJ.Discrete Math,2018,341(5):1406-1418.9ZHU J L,BU Y H.List r-dynamic coloring of graphs with small maximum average degreeJ.Discrete Appl Math,2019,258:254-263.10YI D,ZHU J L,FENG L X,et al.Optimal r-dynamic coloring of sparse graphsJ.J Comb Optim,2019,38(2):545-555.11LA H,MONTASSIER M,PINLOU A,et al.r-hued(r+1)-coloring of planar graphs with girth at least 8 for r9J.European J Combin,2021,91:103219.(责任编辑 陶立方)651浙江师范大学学报(自然科学版)第 47 卷