Complexity of the conditional colorability of graphs

Xueliang Li, Xiangmei Yao, Wenli Zhou

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 t…