4624
правки
Circular coloring of a graph: различия между версиями
Материал из WikiGrapp
нет описания правки
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. | |||
