Article ID Journal Published Year Pages File Type
4648128 Discrete Mathematics 2012 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,