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

Хроматическое число снарка «Цветок» Шаблон:Math равно 3, но цикловое хроматичеcкое число равно $⩽\frac{5}{2}$.

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

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

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

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

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

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

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

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

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

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

$K_{\frac{2}{1}}\to K_{\frac{5}{2}}\to K_{\frac{7}{3}}\to \dots \to K_{\frac{3}{1}}\to K_{\frac{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_{\frac{5}{2}}\approx C_5$, который идёт раньше $K_3$, что соответствует факту, что ${\chi }_c(J_5)⩽2,5<3$.

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья