典型文献
稀疏图与系列平行图的列表动态染色
文献摘要：
图的(列表)动态染色模型可用于解决信道分配中的一些关键问题,是图论和理论计算机科学领域的一个重要的研究方向.Kim和Park(2011)给出了任何最大平均度小于8/3的图的列表动态色数至多为4的证明.然而,由于具有5个顶点的圈C5的最大平均度为2且列表动态色数为5,因此Kim和Park的上述结论是错误的.基于此,本文证明了任何最大平均度小于8/3的普通图(每个连通分支都不与C5同构的图)的列表动态色数至多为4,且该上界4是最优的,从而对Kim和Park的结果进行了修正.与此同时,本文证明了如果图G是系列平行图,则当其是普通图时,其列表动态色数至多为4,且该上界4是最优的,当其不是普通图时,其列表动态色数恰好为5,从而将Song等人(2014)的结果"任何系列平行图的列表动态色数至多为6"进行了改进.
文献关键词：
信道分配问题;动态染色;列表染色;最大平均度;系列平行图
中图分类号：
作者姓名：
张欣;李艳
作者机构：
西安电子科技大学数学与统计学院,西安710071
文献出处：
引用格式：
[1]张欣;李艳-.稀疏图与系列平行图的列表动态染色)[J].应用数学学报,2022(04):552-559
A类：
系列平行图,动态染色,信道分配问题
B类：
稀疏图,图论,计算机科学,科学领域,Kim,Park,最大平均度,色数,至多,顶点,C5,连通分支,上界,恰好,Song,列表染色
AB值：
0.210137
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
