Complexity of conditional colorability of graphs

Xueliang Li, Xueliang Li, Xiangmei Yao, Wenli Zhou, Haitze J. Broersma

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)

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 languageUndefined
Pages (from-to)320-324
Number of pages5
JournalApplied mathematics letters
Volume22
Issue number3
DOIs
Publication statusPublished - Mar 2009

Keywords

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

Cite this