Isotropic coloring

Isotropic coloring --- изотропная раскраска.

The problem of finding a [math]\displaystyle{ (t,i,j) }[/math]-cover of a graph [math]\displaystyle{ G }[/math] is equivalent to the following vertex-coloring problem of [math]\displaystyle{ G }[/math]. Color the vertices of [math]\displaystyle{ G }[/math] in two colors, black and white, such that black vertices correspond to the centers of the covering balls. Thus, the [math]\displaystyle{ t }[/math]-neighborhood of every black vertex contains exactly [math]\displaystyle{ i }[/math] black vertices and the [math]\displaystyle{ t }[/math]-neighborhood of every white vertex contains exactly [math]\displaystyle{ j }[/math] black vertices. A similar coloring problem was introduced by V. Vizing. He considered a distributive or isotropic coloring of a graph, that is, a coloring in which the number of vertices of a fixed color in the 1-neighborhood of any vertex depends only on the color of this vertex.

Let [math]\displaystyle{ \varphi: \; V(G) \rightarrow \{0,1\} }[/math] be a coloring of [math]\displaystyle{ V(G) }[/math]. We call a vertex [math]\displaystyle{ u \in V(G) }[/math] black if [math]\displaystyle{ \varphi(u) = 1 }[/math] and we call a vertex [math]\displaystyle{ u }[/math] white if [math]\displaystyle{ \varphi(u) = 0 }[/math]. For [math]\displaystyle{ u \in V(G) }[/math] and [math]\displaystyle{ k \in \{0,1\} }[/math], let [math]\displaystyle{ N_{t}^{k}(u) }[/math] be the set of vertices of color [math]\displaystyle{ k }[/math] in the [math]\displaystyle{ t }[/math]-neighborhood of [math]\displaystyle{ u }[/math].

A coloring [math]\displaystyle{ \varphi }[/math] of [math]\displaystyle{ G }[/math] is [math]\displaystyle{ (t,i,j) }[/math]-isotropic if every black vertex has exactly [math]\displaystyle{ i }[/math] black vertices within distance [math]\displaystyle{ t }[/math] and every white vertex has exactly [math]\displaystyle{ j }[/math] black vertices within distance [math]\displaystyle{ t }[/math].