2007/11/19 by Xueliang Li, Li, Xueliang, Wenli Zhou +1
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.0711.2844
13 pages
arxiv created 2007/11/19 · arxiv updated 2009/12/01
A \it dynamic k-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least 2 in G will be adjacent to vertices with at least 2 different colors. The smallest number k for which a graph G can have a dynamic k-coloring is the \it dynamic chromatic number, denoted by χd(G). In this paper, we investigate the dynamic 3-colorings of claw-free graphs. First, we prove that it is NP-complete to determine if a claw-free graph with maximum degree 3 is dynamically 3-colorable. Second, by forbidding a kind of subgraphs, we find a reasonable subclass of claw-free graphs with maximum degree 3, for which the dynamically 3-colorable problem can be solved in linear time. Third, we give a linear time algorithm to recognize this subclass of graphs, and a linear time algorithm to determine whether it is dynamically 3-colorable. We also give a linear time algorithm to color the graphs in the subclass by 3 colors.