K-Cyclic chromatic number: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Cyclic chromatic number''' --- <math>k</math>-циклическое хроматическое число. The '''<math>k</math>-cyclic chromati…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Cyclic chromatic number''' - | '''<math>k</math>-Cyclic chromatic number''' — ''[[k-циклическое хроматическое число|<math>\,k</math>-циклическое хроматическое число]]''. | ||
число. | |||
The '''<math>k</math>-cyclic chromatic number''' <math>\chi_{k}(G)</math> of a plane graph is the smallest number of colours in a vertex colouring of <math>G</math> such that no face of | The '''<math>\,k</math>-cyclic chromatic number''' <math>\,\chi_{k}(G)</math> of a [[plane graph]] is the smallest number of colours in a [[vertex]] [[Coloring, colouring|colouring]] of <math>\,G</math> such that no face of size at most <math>\,k</math> has two boundary vertices of the same colour. It is easy to see that the Four Colour Theorem may be stated in the form: | ||
size at most <math>k</math> has two boundary vertices of the same colour. It is | |||
easy to see that the Four Colour Theorem may be stated in the form: | |||
<math>\chi_{3}(G) \leq 4</math> | <math>\,\chi_{3}(G) \leq 4</math> | ||
for every plane graph <math>G</math>. | for every plane graph <math>\,G</math>. | ||
The number <math>\chi_{k}(G)</math> was introduced explicitly by Ore and Plummer | The number <math>\,\chi_{k}(G)</math> was introduced explicitly by Ore and Plummer (1969). | ||
(1969). | |||
==Литература== | |||
*Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Версия от 08:10, 4 декабря 2023
[math]\displaystyle{ k }[/math]-Cyclic chromatic number — [math]\displaystyle{ \,k }[/math]-циклическое хроматическое число.
The [math]\displaystyle{ \,k }[/math]-cyclic chromatic number [math]\displaystyle{ \,\chi_{k}(G) }[/math] of a plane graph is the smallest number of colours in a vertex colouring of [math]\displaystyle{ \,G }[/math] such that no face of size at most [math]\displaystyle{ \,k }[/math] has two boundary vertices of the same colour. It is easy to see that the Four Colour Theorem may be stated in the form:
[math]\displaystyle{ \,\chi_{3}(G) \leq 4 }[/math]
for every plane graph [math]\displaystyle{ \,G }[/math].
The number [math]\displaystyle{ \,\chi_{k}(G) }[/math] was introduced explicitly by Ore and Plummer (1969).
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.