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

Колове розфарбовування можна розглядати, як уточнення звичайного розфарбовування графів. Колове хроматичне число графа ${\displaystyle G}$ з позначенням ${\displaystyle \chi _{c}(G)}$ можна визначити такими еквівалентними (для скінченних графів) способами:

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

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

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

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

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

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

Коловий повний граф
Вершин	n
Ребер	${\displaystyle {\tfrac {n(n-2k+1)}{2}}}$
Обхват	${\displaystyle \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)-регулярний вершинно-транзитивний циркулянтний гамільтонів

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

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

Наприклад, ${\displaystyle K_{\tfrac {n}{1}}}$ є просто повним графом K_n, тоді як граф ${\displaystyle K_{\tfrac {2n+1}{n}}}$ ізоморфний циклічному графу ${\displaystyle C_{2n+1}}$.

У такому разі колове розфарбування, згідно з другим визначенням вище, є гомоморфізмом у коловий повний граф. Важливим твердженням щодо цих графів є те, що ${\displaystyle K_{\tfrac {a}{b}}}$ допускає гомоморфізм у ${\displaystyle K_{\tfrac {c}{d}}}$ тоді й лише тоді, коли ${\displaystyle {\tfrac {a}{b}}\leqslant {\tfrac {c}{d}}}$. Це пояснює використані позначення, оскільки, якщо раціональні числа ${\displaystyle {\tfrac {a}{b}}}$ і ${\displaystyle {\tfrac {c}{d}}}$ рівні, то ${\displaystyle K_{\tfrac {a}{b}}}$ і ${\displaystyle K_{\tfrac {c}{d}}}$ гомоморфно еквівалентні. Більш того, порядок гомоморфізму уточнює порядок, що задається повними графами в (щільний порядок) і відповідає раціональним числам ${\displaystyle \geqslant 2}$. Наприклад,

${\displaystyle 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 }$

Або, еквівалентно,

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

Приклад на малюнку можна інтерпретувати, як гомоморфізм зі снарка «Квітка» ${\displaystyle J_{5}}$ в ${\displaystyle K_{\tfrac {5}{2}}\approx C_{5}}$, який іде раніше від ${\displaystyle K_{3}}$, що відповідає факту, що ${\displaystyle \chi _{c}(J_{5})\leqslant 2,5<3}$.

Див. також

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

Примітки

1. Vince, 1988.

Література

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