K-Colored graph

[math]\displaystyle{ k }[/math]-Colored graph --- [math]\displaystyle{ k }[/math]-раскрашенный граф.

Let [math]\displaystyle{ k }[/math] be an integer. A [math]\displaystyle{ k }[/math]-colored graph is a graph [math]\displaystyle{ G = (V,E) }[/math] together with a vertex coloring which is a mapping [math]\displaystyle{ f: \; V \rightarrow S }[/math] such that

(1) each vertex is colored with one of the colors such that no two adjacent vertices have the same color (i.e., [math]\displaystyle{ f(x) \neq f(y) }[/math] whenever [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are adjacent),

(2) [math]\displaystyle{ |S| = k }[/math] and each color is used at least once (i.e., [math]\displaystyle{ f }[/math] is surjective).