Circular coloring of a graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Circular coloring of a graph''' --- цикловая раскраска графа. An '''<math>r</math>-circular coloring of a graph''' (<math>r</math> is a re…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Circular coloring of a graph''' | '''Circular coloring of a graph''' — ''[[цикловая раскраска графа]].'' | ||
An '''<math>r</math>-circular coloring of a graph''' (<math>r</math> is a real number, <math>r | An '''<math>\,r</math>-circular coloring of a graph''' (<math>\,r</math> is a real number, <math>r | ||
\geq 2</math>) is a mapping <math>\psi: V(G) \rightarrow [0,r)</math> such that <math>1 | \geq 2</math>) is a mapping <math>\psi: V(G) \rightarrow [0,r)</math> such that <math>1 | ||
\leq |\psi(u) - \psi(v)| \leq r-1</math>, whenever <math>uv \in E(G)</math>. A graph <math>G</math> | \leq |\psi(u) - \psi(v)| \leq r-1</math>, whenever <math>uv \in E(G)</math>. A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> | ||
is called '''<math>r</math>-circular colorable''' if it admits an <math>r</math>-circular | is called '''<math>\,r</math>-circular colorable''' if it admits an <math>\,r</math>-circular | ||
coloring. The '''circular chromatic number''' of <math>G</math>, denoted by | coloring. The '''circular chromatic number''' of <math>\,G</math>, denoted by | ||
<math>\chi_{c}(G)</math>, is the smallest value for <math>r</math> such that <math>G</math> is | <math>\chi_{c}(G)</math>, is the smallest value for <math>\,r</math> such that <math>\,G</math> is | ||
<math>r</math>-circular colorable. | <math>\,r</math>-circular colorable. | ||
The concept of a circular coloring was first introduced in 1988 by | The concept of a circular coloring was first introduced in 1988 by | ||
Vince who first called it a '''star coloring''', and it was given | Vince who first called it a '''star coloring''', and it was given | ||
the current name by Zhu. | the current name by Zhu. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:44, 13 июня 2013
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.