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

来源：应用数学学报杂志2022年第4期北京时间：

作者：张欣, 李艳

单位：西安电子科技大学数学与统计学院, 西安 710071

摘要：图的（列表）动态染色模型可用于解决信道分配中的一些关键问题，是图论和理论计算机科学领域的一个重要的研究方向.Kim和Park （2011）给出了任何最大平均度小于8/3的图的列表动态色数至多为4的证明.然而，由于具有5个顶点的圈$C_5$的最大平均度为2且列表动态色数为5，因此Kim和Park的上述结论是错误的.基于此，本文证明了任何最大平均度小于8/3的普通图（每个连通分支都不与$C_5$同构的图）的列表动态色数至多为4，且该上界4是最优的，从而对Kim和Park的结果进行了修正.与此同时，本文证明了如果图$G$是系列平行图，则当其是普通图时，其列表动态色数至多为4，且该上界4是最优的，当其不是普通图时，其列表动态色数恰好为5，从而将Song等人（2014）的结果"任何系列平行图的列表动态色数至多为6"进行了改进.

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