图的(列表)动态染色模型可用于解决信道分配中的一些关键问题,是图论和理论计算机科学领域的一个重要的研究方向.Kim和Park (2011)给出了任何最大平均度小于8/3的图的列表动态色数至多为4的证明.然而,由于具有5个顶点的圈的最大平均度为2且列表动态色数为5,因此Kim和Park的上述结论是错误的.基于此,本文证明了任何最大平均度小于8/3的普通图(每个连通分支都不与同构的图)的列表动态色数至多为4,且该上界4是最优的,从而对Kim和Park的结果进行了修正.与此同时,本文证明了如果图是系列平行图,则当其是普通图时,其列表动态色数至多为4,且该上界4是最优的,当其不是普通图时,其列表动态色数恰好为5,从而将Song等人(2014)的结果"任何系列平行图的列表动态色数至多为6"进行了改进.
Abstract
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.
关键词
信道分配问题 /
动态染色 /
列表染色 /
最大平均度 /
系列平行图
{{custom_keyword}} /
Key words
channel assignment problem /
dynamic coloring /
list coloring /
maximum average degree /
series-parallel graph
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Niu B, Zhang X. On (p,1)-total labelling of some 1-planar graphs. Discuss. Math. Graph Theory, 2021, 41(2):531-558
[2] Yeh R K. Labelling graphs with a condition at distance two. Ph.D Thesis, Dept. of Math.,Univ. of South Carolina, Columbia, SC, USA, 1990
[3] Griggs J R, Yeh R K. Labeling graphs with a condition at distance two. SIAM J. Discrete Math., 1992, 5:586-595
[4] Zhu J, Bu Y. List r-dynamic coloring of sparse graphs. Theoret. Comput. Sci., 2020, 817:1-11
[5] Diestel R. Graph Theory (5th edition). Berlin:Springer, 2016
[6] 徐俊明. 图论及其应用(第4版). 合肥:中国科学技术大学出版社, 2019(Xu J M. Graph Theory with Applications (Fourth edition). Hefei:University of Science and Technology of China Press, 2019)
[7] Kim S J, Lee S J, Park W J. Dynamic coloring and list dynamic coloring of planar graphs. Discrete Appl. Math., 2013, 161:2207-2212
[8] Kim Y, Lee S J, Oum S. Dynamic coloring of graphs having no K5 minor. Discrete Appl. Math., 2016, 206:81-89
[9] Akbari S, Ghanbari M, Jahanbekam S. On the list dynamic coloring of graphs. Discrete Appl. Math., 2009, 157:3005-3007
[10] Kim S J, Park W J. List dynamic coloring of sparse graphs. Lecture Notes in Comput. Sci., 2011, 6831:156-162
[11] Song H, Fan S, Chen Y, Sun L, et al. On r-hued coloring of K4-minor free graphs. Discrete Math., 2014, 315-316:47-52
[12] Juvan M, Mohar B, Thomas R. List edge-colorings of series-parallel graphs. Electron. J. Combin., 1999, 6:R42
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金面上基金(11871055),西安市科协青年人才托举计划(2018-6),国家留学基金委公派留学(访问学者)(201906965003)资助项目.
{{custom_fund}}