(k,d)-Coloring

Материал из WikiGrapp
Перейти к:навигация, поиск

\,(k,d)-Coloring\,(k,d)-раскраска.

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

Литература

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