Dynamic 3-Coloring of Claw-free Graphs
| dc.creator | Li, Xueliang | |
| dc.creator | Zhou, Wenli | |
| dc.date | 2007-11-19 | |
| dc.date.accessioned | 2026-07-07T08:43:41Z | |
| dc.date.available | 2026-07-07T08:43:41Z | |
| dc.description | 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. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0711.2844 | |
| dc.identifier | http://arxiv.org/abs/0711.2844 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142400 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Computational Complexity | |
| dc.subject | G.2.2; F.2.2 | |
| dc.title | Dynamic 3-Coloring of Claw-free Graphs | |
| dc.type | text |