### Abstract

For positive integers $k$ and $r$, 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, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.

Original language | Undefined |
---|---|

Pages (from-to) | 320-324 |

Number of pages | 5 |

Journal | Applied mathematics letters |

Volume | 22 |

Issue number | 3 |

DOIs | |

Publication status | Published - Mar 2009 |

### Keywords

- Conditional coloring
- METIS-264415
- NP-complete
- (Conditional) chromatic number
- Vertex coloring
- Algorithm
- Complexity
- EWI-15829
- IR-67841

## Cite this

Li, X., Li, X., Yao, X., Zhou, W., & Broersma, H. J. (2009). Complexity of conditional colorability of graphs.

*Applied mathematics letters*,*22*(3), 320-324. https://doi.org/10.1016/j.aml.2008.04.003