Back to Search
Start Over
The 2nd-order conditional 3-coloring of claw-free graphs
- Source :
-
Theoretical Computer Science . May2008, Vol. 396 Issue 1-3, p151-157. 7p. - Publication Year :
- 2008
-
Abstract
- Abstract: A 2nd-order conditional -coloring of a graph is a proper -coloring of the vertices of such that every vertex of degree at least 2 in will be adjacent to vertices with at least 2 different colors. The smallest number for which a graph can have a 2nd-order conditional -coloring is the 2nd-order conditional chromatic number, denoted by . In this paper, we investigate the 2nd-order conditional 3-colorings of claw-free graphs. First, we prove that it is -complete to determine if a claw-free graph with maximum degree 3 is 2nd-order conditionally 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 2nd-order conditionally 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 2nd-order conditionally 3-colorable. We also give a linear time algorithm to color the graphs in the subclass by 3 colors. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 396
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 31755077
- Full Text :
- https://doi.org/10.1016/j.tcs.2008.01.034