K-Cyclic chromatic number: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''<math>k</math>-Cyclic chromatic number''' --- <math>k</math>-циклическое хроматическое число. The '''<math>k</math>-cyclic chromati…»)
 
Нет описания правки
Строка 1: Строка 1:
'''<math>k</math>-Cyclic chromatic number''' --- <math>k</math>-циклическое хроматическое
'''<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.

Навигация