### Abstract

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

*Applied mathematics letters*,

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

}

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

**Complexity of conditional colorability of graphs.** / Li, Xueliang; Li, Xueliang; Yao, Xiangmei; Zhou, Wenli; Broersma, Haitze J.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Complexity of conditional colorability of graphs

AU - Li, Xueliang

AU - Li, Xueliang

AU - Yao, Xiangmei

AU - Zhou, Wenli

AU - Broersma, Haitze J.

N1 - eemcs-eprint-15829

PY - 2009/3

Y1 - 2009/3

N2 - 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.

AB - 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.

KW - Conditional coloring

KW - METIS-264415

KW - NP-complete

KW - (Conditional) chromatic number

KW - Vertex coloring

KW - Algorithm

KW - Complexity

KW - EWI-15829

KW - IR-67841

U2 - 10.1016/j.aml.2008.04.003

DO - 10.1016/j.aml.2008.04.003

M3 - Article

VL - 22

SP - 320

EP - 324

JO - Applied mathematics letters

JF - Applied mathematics letters

SN - 0893-9659

IS - 3

ER -