Computer Science – Discrete Mathematics
Scientific paper
2007-11-19
Computer Science
Discrete Mathematics
13 pages
Scientific paper
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 $\chi_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.
Li Xueliang
Zhou Wenli
No associations
LandOfFree
Dynamic 3-Coloring of Claw-free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic 3-Coloring of Claw-free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic 3-Coloring of Claw-free Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-115558