Колове розфарбовування

Колове розфарбовування можна розглядати, як уточнення звичайного розфарбовування графів. Колове хроматичне число графа $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$.

Хроматичне число снарка «Квітка» J₅ дорівнює 3, але колове хроматичне число $\leqslant {\tfrac {5}{2}}$.

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

Колове розфарбування спочатку визначив Вінс, який назвав його «зірковим розфарбуванням».

Колове розфарбування двоїсте суб'єкту ніде не нульового потоку і більш того, колове розфарбування має природне двоїсте поняття «коловий потік».

Колові повні графи

Коловий повний граф
Вершин	n
Ребер	${\tfrac {n(n-2k+1)}{2}}$
Обхват	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leqslant n<3k\\3&{\text{в решті випадків}}\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$.

Див. також

• Циклічний ранг

Література

• 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.