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

Хроматическое число снарка «Цветок» J₅ равно 3, но цикловое хроматичеcкое число равно [math]\displaystyle{ \leqslant \tfrac{5}{2} }[/math].

Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа [math]\displaystyle{ G }[/math] с обозначением [math]\displaystyle{ \chi_c(G) }[/math] можно определить следующими эквивалентными (для конечных графов) способами.

1. [math]\displaystyle{ \chi_c(G) }[/math] равен инфимуму по всем вещественным числам [math]\displaystyle{ r }[/math] таким, что существует отображение из [math]\displaystyle{ V(G) }[/math] в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии [math]\displaystyle{ \geqslant \tfrac{1}{r} }[/math] вдоль окружности.
2. [math]\displaystyle{ \chi_c(G) }[/math] равен инфимуму по рациональным числам [math]\displaystyle{ \tfrac{n}{k} }[/math] таким, что существует отображение из [math]\displaystyle{ V(G) }[/math] в циклическую группу [math]\displaystyle{ {\mathbb Z}/n{\mathbb Z} }[/math] со свойством, что смежные вершины отображаются в элементы на расстоянии [math]\displaystyle{ \geqslant k }[/math] друг от друга.
3. В ориентированном графе определим дисбаланс цикла [math]\displaystyle{ C }[/math], как значение [math]\displaystyle{ |E(C)| }[/math], делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, [math]\displaystyle{ \chi_c(G) }[/math] равен минимальному дисбалансу по всем ориентациям графа [math]\displaystyle{ G }[/math].

Относительно несложно видеть, что [math]\displaystyle{ \chi_c(G) \leqslant \chi(G) }[/math] (используя определение 1 или 2), но, фактически, [math]\displaystyle{ \lceil \chi_c(G) \rceil = \chi(G) }[/math]. В этом смысле мы говорим, что цикловое хроматичеcкое число уточняет обычное хроматическое число.

Цикловую раскраску первоначально определил Винс, который назвал её «звёздной раскраской».

Цикловая раскраска двойственна субъекту нигде не нулевого потока и более того, цикловая раскраска имеет естественное двойственное понятие «циркуляционный поток».

Цикловые полные графы

Циркулярный полный граф
Вершин	n
Рёбер	[math]\displaystyle{ \tfrac{n(n-2k+1)}{2}, }[/math]
Обхват	[math]\displaystyle{ \left\{\begin{array}{ll}\infty & n = 2k\\ n & n = 2k+1\\ 4 & 2k+2 \leq n \lt 3k \\ 3 & \text{otherwise}\end{array}\right. }[/math]
Хроматическое число	⌈n/k⌉
Свойства	(n − 2k + 1)- регулярный Вершинно-транзитивный Циркулянтный Гамильтонов

Для целых [math]\displaystyle{ n,k }[/math] таких, что [math]\displaystyle{ n\geqslant 2k }[/math], цикловой полный граф [math]\displaystyle{ K_{\tfrac{n}{k}} }[/math] (известный также как цикловая клика) — это граф с множеством вершин [math]\displaystyle{ {\mathbb Z}/n{\mathbb Z} }[/math] и рёбрами между элементами на расстоянии [math]\displaystyle{ \geqslant k }[/math] друг от друга. То есть, вершинами являются числа [math]\displaystyle{ {0, 1, ..., ''n''-1} }[/math] и вершина i смежна с:

[math]\displaystyle{ i+k, i+k+1, \dots, i+n-k \mod n }[/math].

Например, [math]\displaystyle{ K_{\tfrac{n}{1}} }[/math] является просто полным графом K_n, в то время как граф [math]\displaystyle{ K_{\tfrac{2n+1}{n}} }[/math] изоморфен графу-циклу [math]\displaystyle{ C_{2n+1} }[/math].

В таком случае цикловая раскраска, согласно второму определению выше, является гомоморфизмом в цикловой полный граф. Критическое обстоятельство об этих графах заключается в том, что [math]\displaystyle{ K_{\tfrac{a}{b}} }[/math] допускает гомоморфизм в [math]\displaystyle{ K_{\tfrac{c}{d}} }[/math] тогда и только тогда, когда [math]\displaystyle{ \tfrac{a}{b} \leqslant \tfrac{c}{d} }[/math]. Это объясняет обозначение, поскольку если рациональные числа [math]\displaystyle{ \tfrac{a}{b} }[/math] и [math]\displaystyle{ \tfrac{c}{d} }[/math] равны, то [math]\displaystyle{ K_{\tfrac{a}{b}} }[/math] и [math]\displaystyle{ K_{\tfrac{c}{d}} }[/math] гомоморфно эквивалентны. Более того, порядок гомоморфизма уточняет порядок, задаваемый полными графами в плотный порядок и соответствует рациональным числам [math]\displaystyle{ \geqslant 2 }[/math]. Например

[math]\displaystyle{ K_{\tfrac{2}{1}} \to K_{\tfrac{5}{2}} \to K_{\tfrac{7}{3}} \to \dots \to K_{\tfrac{3}{1}} \to K_{\tfrac{4}{1}} \to \dots }[/math]

Или, эквивалентно

[math]\displaystyle{ K_2 \to C_5 \to C_7 \to \dots \to K_3 \to K_4 \to \dots }[/math]

Пример на рисунке можно интерпретировать, как гомоморфизм из снарка «Цветок» [math]\displaystyle{ J_5 }[/math] в [math]\displaystyle{ K_{\tfrac{5}{2}} \approx C_5 }[/math], который идёт раньше [math]\displaystyle{ K_3 }[/math], что соответствует факту, что [math]\displaystyle{ \chi_c(J_5) \leqslant 2,5 \lt 3 }[/math].

См. также

• Циклический ранг