Backbone coloring

Backbone coloring — хребтовая раскраска.

Consider a graph [math]\displaystyle{ \,G = (V,E) }[/math] with a spanning tree [math]\displaystyle{ \,T = (V,E_{T}) }[/math] (backbone). A vertex coloring [math]\displaystyle{ f: V \rightarrow \{1,2, \ldots \} }[/math] is proper, if [math]\displaystyle{ |f(u) - f(v)| \geq 1 }[/math] holds for all edges [math]\displaystyle{ (u,v) \in E }[/math]. A vertex coloring is a backbone coloring for [math]\displaystyle{ \,(G,T) }[/math], if it is proper and, additionally, [math]\displaystyle{ |f(u) - f(v)| \geq 2 }[/math] holds for all edges [math]\displaystyle{ (u,v) \in E_{T} }[/math] in the spanning tree [math]\displaystyle{ \,T }[/math].

The backbone coloring number [math]\displaystyle{ \,BBC(G,T) }[/math] of [math]\displaystyle{ \,(G,T) }[/math] is the smal-lest integer [math]\displaystyle{ \ell }[/math] for which a backbone coloring [math]\displaystyle{ f: V \rightarrow \{1, 2, \ldots, \ell\} }[/math] exists.

Литература

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