Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648128 | Discrete Mathematics | 2012 | 5 Pages |
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.