Цикловая раскраска
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ec/J5_circular_color.svg/300px-J5_circular_color.svg.png)
Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа с обозначением можно определить следующими эквивалентными (для конечных графов) способами.
- равен инфимуму по всем вещественным числам таким, что существует отображение из в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии вдоль окружности.
- равен инфимуму по рациональным числам таким, что существует отображение из в циклическую группу со свойством, что смежные вершины отображаются в элементы на расстоянии друг от друга.
- В ориентированном графе определим дисбаланс цикла , как значение , делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, равен минимальному дисбалансу по всем ориентациям графа .
Относительно несложно видеть, что (используя определение 1 или 2), но, фактически, . В этом смысле мы говорим, что цикловое хроматичеcкое число уточняет обычное хроматическое число.
Цикловую раскраску первоначально определил Винс[1], который назвал её «звёздной раскраской».
Цикловая раскраска двойственна субъекту нигде не нулевого потока и более того, цикловая раскраска имеет естественное двойственное понятие «циркуляционный поток».
Цикловые полные графы
[править | править код]Циркулярный полный граф | |
---|---|
Вершин | n |
Рёбер | |
Обхват | |
Хроматическое число | ⌈n/k⌉ |
Свойства |
(n − 2k + 1)- регулярный Вершинно-транзитивный Циркулянтный Гамильтонов |
Для целых таких, что , цикловой полный граф (известный также как цикловая клика) — это граф с множеством вершин и рёбрами между элементами на расстоянии друг от друга. То есть, вершинами являются числа и вершина i смежна с:
- .
Например, является просто полным графом Kn, в то время как граф изоморфен графу-циклу .
В таком случае цикловая раскраска, согласно второму определению выше, является гомоморфизмом в цикловой полный граф. Критическое обстоятельство об этих графах заключается в том, что допускает гомоморфизм в тогда и только тогда, когда . Это объясняет обозначение, поскольку если рациональные числа и равны, то и гомоморфно эквивалентны. Более того, порядок гомоморфизма уточняет порядок, задаваемый полными графами в плотный порядок и соответствует рациональным числам . Например
Или, эквивалентно
Пример на рисунке можно интерпретировать, как гомоморфизм из снарка «Цветок» в , который идёт раньше , что соответствует факту, что .
См. также
[править | править код]Примечания
[править | править код]Литература
[править | править код]- Adam Nadolski. Circular coloring of graphs // Graph colorings. — Providence, RI: Amer. Math. Soc., 2004. — Т. 352. — С. 123–137. — (Contemp. Math.). — doi:10.1090/conm/352/09.
- Vince A. Star chromatic number // Journal of Graph Theory. — 1988. — Т. 12, вып. 4. — С. 551–559. — doi:10.1002/jgt.3190120411.
- Zhu X. Circular chromatic number, a survey // Discrete Mathematics. — 2001. — Т. 229, вып. 1-3. — С. 371–410. — doi:10.1016/S0012-365X(00)00217-X.