Backbone coloring

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

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

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

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

Литература

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