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

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

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

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

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

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

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

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

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

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

$i+k,i+k+1,\dots ,i+n-k\mod n$.

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

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

$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$

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

$K_{2}\to C_{5}\to C_{7}\to \dots \to K_{3}\to K_{4}\to \dots$

Пример на рисунке можно интерпретировать, как гомоморфизм из снарка «Цветок» $J_{5}$ в $K_{\tfrac {5}{2}}\approx C_{5}$, который идёт раньше $K_{3}$, что соответствует факту, что $\chi _{c}(J_{5})\leqslant 2,5<3$.

См. также

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