کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648128 | 1342394 | 2012 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the difference between chromatic number and dynamic chromatic number of graphs On the difference between chromatic number and dynamic chromatic number of graphs](/preview/png/4648128.png)
A proper vertex kk-coloring of a graph GG is called dynamic , if there is no vertex v∈V(G)v∈V(G) with d(v)≥2d(v)≥2 and all of its neighbors have the same color. The smallest integer kk such that GG has a kk-dynamic coloring is called the dynamic chromatic number of GG and denoted by χ2(G)χ2(G). We say that v∈V(G)v∈V(G) in a proper vertex coloring of GG is a bad vertex if d(v)≥2d(v)≥2 and only one color appears in the neighbors of vv. In this paper, we show that if GG is a graph with the chromatic number at least 66, then there exists a proper vertex χ(G)χ(G)-coloring of GG such that the set of bad vertices of GG is an independent set. Also, we provide some upper bounds for χ2(G)−χ(G)χ2(G)−χ(G) in terms of some parameters of the graph GG.
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2579–2583