Circular coloring of a graph

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.