On the complexity of graph coloring with additional local conditions

Abstract

Let $G=(V,E)$ be a finite simple graph. Recall that a proper coloring of $G$ is a mapping $\phi :V\to \{1,\dots ,k\}$ such that every color class induces an independent set. Such a $\phi$ 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⩾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.

arXiv comment4 pages