Хроматичне число

Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G).

Хроматичне число графа — мінімальне число ${\displaystyle k}$, таке що множину ${\displaystyle V}$ вершин графа можна розбити на ${\displaystyle k}$ класів ${\displaystyle C_{1},C_{2},\ldots ,C_{k}}$, що не перетинаються:

${\displaystyle V=\bigcup _{i}^{}C_{i};\ C_{i}\cap C_{j}=\varnothing ,}$

таких, що вершини в кожному класі незалежні, тобто будь-яке ребро графа не з'єднує вершини одного й того ж класу.

• K-розфарбовний граф — граф, хроматичне число якого не перевищує ${\displaystyle K}$. Тобто його вершини можна розфарбувати ${\displaystyle K}$ різними кольорами так, що кінці будь-якого ребра будуть різних кольорів.
• K-хроматичний граф — граф, хроматичне число якого дорівнює ${\displaystyle K}$.

Хроматичний клас графа G — мінімальна кількість кольорів , в які можна розфарбувати ребра графа G так, щоб суміжні ребра були різних кольорів. Позначається χ'(G). Проблема ребрового розфарбування довільного плаского кубічного графа без мостів трьома кольорами еквівалентна відомій Проблемі чотирьох фарб. Реброве розфарбування визначає 1-факторизацію графа.

Якщо розглядати кількість відмінних розфарбувань позначеного графа як функцію від доступної кількості кольорів t, то з'ясується, що ця функція завжди буде поліномом від t. Цей факт був виявлений Біркгофом і Д. С. Люїсом-мол.^[1] при спробі довести гіпотезу чотирьох фарб.

Розглянемо граф, зображений на малюнку. Використовуючи лише три кольори, існує 12 варіантів розфарбування. З двома кольорами його взагалі не можна розфарбувати. З чотирма, він може бути розфарбований у 24 + 4*12 = 72 спосіб: використання всіх чотирьох дає 4! = 24 правильних розфарбувань; і для кожного вибору 3-х з 4-х доступних кольорів маємо 12 варіантів. Таким чином, таблиця кількості правильних розфарбувань виглядає таким чином:

Хроматичний многочлен — функція P(G, t), яка рахує кількість t-розфарбувань G. Для графа з малюнка P(G, t) = t(t − 1)²(t − 2), і насправді, P(G, 4) = 72.

Хроматичні многочлени деяких графів

Трикутник ${\displaystyle K_{3}}$	${\displaystyle t(t-1)(t-2)}$
Повний граф ${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)...(t-(n-1))}$
Дерево с ${\displaystyle n}$ вершинами	${\displaystyle t(t-1)^{n-1}}$
Цикл ${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Граф Петерсена	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Також хроматичне число можна розглядати для інших об'єктів, наприклад, для метричних просторів. Так хроматичним числом площини називається мінімальне число χ таке, що існує розфарбування всіх точок площини в один із χ кольорів і при цьому ніякі дві точки одного кольору не розташовані на відстані 1 одна від одної (площина не містить монохроматичних відрізків довжини 1). Аналогічно для простору будь-якої розмірності.

Багато глибоких задач теорії графів легко формулюються в термінах розфарбовування. Найвідоміша з-посеред таких задач, проблема чотирьох фарб, на сьогодні розв'язана, однак з'являються нові, наприклад, узагальнення проблеми чотирьох фарб, гіпотеза Хадвігера.

• Хроматичний індекс
• Критичний граф
• Дробове розфарбування