(k,d)-Coloring

[math]\displaystyle{ (k,d) }[/math]-Coloring --- [math]\displaystyle{ (k,d) }[/math]-раскраска.

Let [math]\displaystyle{ k }[/math] and [math]\displaystyle{ d }[/math] be positive integers such that [math]\displaystyle{ k \geq 2d }[/math]. A [math]\displaystyle{ (k,d) }[/math]-coloring of a graph [math]\displaystyle{ G = (V,E) }[/math] is a mapping [math]\displaystyle{ c: V \rightarrow Z_{k} = \{0,1, \ldots, k-1\} }[/math] such that, for each edge [math]\displaystyle{ (u,v) \in E }[/math], [math]\displaystyle{ |c(u) - c(v)|_{k} \geq d }[/math], where [math]\displaystyle{ |x|_{k} = \min\{|x|,k-|x|\} }[/math]. This generalizes a usual notion of a [math]\displaystyle{ k }[/math]-coloring: an ordinary [math]\displaystyle{ k }[/math]-coloring of [math]\displaystyle{ G }[/math] is just a [math]\displaystyle{ (k,1) }[/math]-coloring.