Complexity of conditional colorability of graphs

Xueliang Li*, Xiangmei Yao, Wenli Zhou, Hajo Broersma*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)


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


  • Conditional coloring
  • NP-complete
  • (Conditional) chromatic number
  • Vertex coloring
  • Algorithm
  • Complexity


Dive into the research topics of 'Complexity of conditional colorability of graphs'. Together they form a unique fingerprint.

Cite this