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).

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.