首页 | 本学科首页   官方微博 | 高级检索  
     检索      


List 3-dynamic coloring of graphs with small maximum average degree
Authors:Seog-Jin Kim  Boram Park
Institution:1. Department of Mathematics Education, Konkuk University, Seoul, Republic of Korea;2. Department of Mathematics, Ajou University, Suwon, Republic of Korea
Abstract:An r-dynamic k-coloring of a graph G is a proper k-coloring such that for any vertex v, there are at least min{r,degG(v)} distinct colors in NG(v). The r-dynamic chromatic numberχrd(G) of a graph G is the least k such that there exists an r-dynamic k-coloring of G. The listr-dynamic chromatic number of a graph G is denoted by chrd(G).Recently, Loeb et al. (0000) showed that the list 3-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have χ3d(G)4,5, or 6. On the other hand, Song et al. (2016) showed that if G is planar with girth at least 6, then χrd(G)r+5 for any r3.In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that ch3d(G)6 if mad(G)<187, ch3d(G)7 if mad(G)<145, and ch3d(G)8 if mad(G)<3. All of the bounds are tight.
Keywords:Dynamic coloring  List 3-dynamic coloring  Maximum average degree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号