2017/12/08 by Shitov, Yaroslav
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.03150
Let G = (V,E) be a finite simple graph. Recall that a proper coloring of G is a mapping φ: V→\1,…,k\ such that every color class induces an independent set. Such a φ 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.