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

Литература

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