Circular coloring of a graph

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

Circular coloring of a graphцикловая раскраска графа.

An \,r-circular coloring of a graph (\,r is a real number, r
\geq 2) is a mapping \psi: V(G) \rightarrow [0,r) such that 1
\leq |\psi(u) - \psi(v)| \leq r-1, whenever uv \in E(G). A graph \,G is called \,r-circular colorable if it admits an \,r-circular coloring. The circular chromatic number of \,G, denoted by \chi_{c}(G), is the smallest value for \,r such that \,G is \,r-circular colorable.

The concept of a circular coloring was first introduced in 1988 by Vince who first called it a star coloring, and it was given the current name by Zhu.


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