Circular coloring of a graph

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

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