K-Cyclic chromatic number
Перейти к навигации
Перейти к поиску
[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.