  Let $G = (V,E)$ be a finite simple graph. Recall that a proper coloring of
$G$ is a mapping $\varphi: V\to\{1,\ldots,k\}$ such that every color class
induces an independent set. Such a $\varphi$ is called a semi-matching coloring
if the union of any two consecutive color classes induces a matching. We show
that the semi-matching coloring problem is NP-complete for any fixed
$k\geqslant 3$, and we get the same result for another version of this problem
in which any triangle of G is required to have vertices whose colors differ at
least by three.

Combinatorics