稀疏图与系列平行图的列表动态染色  

List Dynamic Coloring of Sparse Graphs and Series-Parallel Graphs

作　　者：张欣 李艳 ZHANG XIN;LI YAN(School of Mathematics and Statistics,Xidian University,Xi'an 710071,China)

机构地区：[1]西安电子科技大学数学与统计学院,西安710071

出　　处：《应用数学学报》2022年第4期552-559,共8页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金面上基金(11871055);西安市科协青年人才托举计划(2018-6);国家留学基金委公派留学(访问学者)(201906965003)资助项目.

摘　　要：图的(列表)动态染色模型可用于解决信道分配中的-些关键问题,是图论和理论计算机科学领域的一个重要的研究方向Kim和Park(2011)给出了任何最大平均度小于8/3的图的列表动态色数至多为4的证明.然而,由于具有5个顶点的圈Cs的最大平均度为2且列表动态色数为5,因此Kim和Park的上述结论是错误的.基于此,本文证明了任何最大平均度小于8/3的普通图(每个连通分支都不与C5同构的图)的列表动态色数至多为4,且该上界4是最优的,从而对Kim和Park的结果进行了修正.与此同时,本文证明了如果图G是系列平行图,则当其是普通图时,其列表动态色数至多为4,且该上界4是最优的,当其不是普通图时,其列表动态色数恰好为5,从而将Song等人(2014)的结果“任何系列平行图的列表动态色数至多为6”进行了改进.The(list)dynamic coloring,an important research direction in graph theory and theoretical computer science,can be used to solve some critical problems on the channel assignment problem.Kim and Park(2011)announced that the list dynamic chromatic number of every graph with maximum average degree less than 8/3 is at most 4.However,this result is incorrect since the cycle C5 on five vertices has maximum average degree 2 and list dynamic chromatic number 5.In this paper,we correct this flaw by proving that the list dynamic chromatic number of every graph with maximum average degree less than 8/3 is at most 4(being sharp)if it is a normal graph,which is a graph having no component isomorphic to C5.Meanwhile,we prove that every series-parallel graph has list dynamic chromatic number at most 4 if it is a normal graph,and exactly 5 otherwise,which improves a result of Song et al.(2014)that states that the list dynamic chromatic number of every series-parallel graph is at most 6.

关 键 词：信道分配问题 动态染色 列表染色 最大平均度 系列平行图 

分 类 号：O157.5[理学—数学]