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

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

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

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

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

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

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

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

Циркулярный полный граф
Вершин	n
Рёбер	$\frac{n(n-<!--\; -\; -->2k+1)}{2},$${\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,k$  таких, что $n⩾<!--\; ⩾\; -->2k$$n\geqslant 2k$ , цикловой полный граф $K_{\frac{n}{k}}$$K_{\tfrac {n}{k}}$  (известный также как цикловая клика) — это граф с множеством вершин $\mathbb{Z}/n\mathbb{Z}$${\mathbb {Z} }/n{\mathbb {Z} }$  и рёбрами между элементами на расстоянии $⩾<!--\; ⩾\; -->k$$\geqslant k$  друг от друга. То есть, вершинами являются числа $0,1,...{,}^{″}{n}^{″}-<!--\; -\; -->1$${0,1,...,''n''-1}$  и вершина i смежна с:

$i+k,i+k+1,\dots <!--\; \dots \; -->,i+n-<!--\; -\; -->k\mathrm{mod}n$$i+k,i+k+1,\dots ,i+n-k\mod n$ .

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

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

$K_{\frac{2}{1}}\to <!--\; \to \; -->K_{\frac{5}{2}}\to <!--\; \to \; -->K_{\frac{7}{3}}\to <!--\; \to \; -->\cdots <!--\; \cdots \; -->\to <!--\; \to \; -->K_{\frac{3}{1}}\to <!--\; \to \; -->K_{\frac{4}{1}}\to <!--\; \to \; -->\dots <!--\; \dots \; -->$$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 <!--\; \to \; -->C_5\to <!--\; \to \; -->C_7\to <!--\; \to \; -->\cdots <!--\; \cdots \; -->\to <!--\; \to \; -->K_3\to <!--\; \to \; -->K_4\to <!--\; \to \; -->\dots <!--\; \dots \; -->$$K_{2}\to C_{5}\to C_{7}\to \dots \to K_{3}\to K_{4}\to \dots$ 

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

См. такжеПравить

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