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

Розфарбовування графа Петерсена у 3 кольори.

Визначення

ред.

Хроматичне число графа — мінімальне число  , таке що множину   вершин графа можна розбити на   класів  , що не перетинаються:

 

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

Пов'язані визначення

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

Реброве розфарбування

ред.
 
Реброве розфарбування кубічного графа

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

Хроматичний многочлен

ред.
 
Цей граф може бути розфарбувати у 3 кольори 12-ма способами.

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

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

Доступно кольорів 1 2 3 4
Кількість розфарбувань 0 0 12 72

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

Хроматичні многочлени деяких графів
Трикутник    
Повний граф    
Дерево с   вершинами  
Цикл    
Граф Петерсена  

Узагальнення

ред.

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

Значення для теорії графів

ред.

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

Див. також

ред.

Примітки

ред.
  1. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.