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

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

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

Колове розфарбування спочатку визначив ВінсШаблон: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$.

Див. також

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

Література

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