K-Циклическая раскраска

Материал из WikiGrapp
Перейти к:навигация, поиск

k-Циклическая раскраска (k-Cyclic colouring) — раскраска вершин плоского графа, при которой для каждой грани размера не больше k все граничные вершины окрашены в различные цвета. Наименьшее число цветов, необходимых для k-циклической раскраски, обозначается x_{k}(G) и называется циклическим хроматическим числом.

Литература

  • [J. Graph Theory]