Complexity of the conditional colorability of graphs

Details Complexity of the conditional colorability of graphs Complexity of the conditional colorability of graphs

2007-11-19

arxiv.org/abs/0711.2843v1

Computer Science

Discrete Mathematics

8 pages

Scientific paper

For an integer $r>0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $min\{r, d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number, denoted by $\chi_r(G)$. It is easy to see that the conditional coloring is a generalization of the traditional vertex coloring for which $r=1$. In this paper, we consider the complexity of the conditional colorings of graphs. The main result is that the conditional $(3,2)$-colorability is $NP$-complete for triangle-free graphs with maximum degree at most 3, which is different from the old result that the traditional 3-colorability is polynomial solvable for graphs with maximum degree at most 3. This also implies that it is $NP$-complete to determine if a graph of maximum degree 3 is $(3,2)$- or $(4,2)$-colorable. Also we have proved that some old complexity results for traditional colorings still hold for the conditional colorings.

Affiliated with

Also associated with

No associations

Rating

Complexity of the conditional colorability of 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 Complexity of the conditional colorability of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of the conditional colorability of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115551