id: 05279830
dt: j
an: 05279830
au: Li, Xueliang; Zhou, Wenli
ti: The 2nd-order conditional 3-coloring of claw-free graphs.
so: Theor. Comput. Sci. 396, No. 1-3, 151-157 (2008).
py: 2008
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: claw-free graph; vertex-coloring; 2nd-order conditional-coloring; 2nd-order
    conditional chromatic number; NP-complete; linear time algorithm
ci: 
li: doi:10.1016/j.tcs.2008.01.034
ab: Summary: A 2nd-order conditional $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
    2nd-order conditional $k$-coloring is the 2nd-order conditional
    chromatic number, denoted by $χ_{ d}(G)$. In this paper, we
    investigate the 2nd-order conditional 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 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.
rv: