Цикловая раскраска

Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа с обозначением можно определить следующими эквивалентными (для конечных графов) способами.

  1. равен инфимуму по всем вещественным числам таким, что существует отображение из в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии вдоль окружности.
  2. равен инфимуму по рациональным числам таким, что существует отображение из в циклическую группу со свойством, что смежные вершины отображаются в элементы на расстоянии друг от друга.
  3. В ориентированном графе определим дисбаланс цикла , как значение , делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, равен минимальному дисбалансу по всем ориентациям графа .
Хроматическое число снарка «Цветок» J5 равно 3, но цикловое хроматичеcкое число равно .

Относительно несложно видеть, что (используя определение 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.