Хроматичне число
Хроматичне число графу G — мінімальна кількість кольорів, в які можна розфарбувати вершини графу G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G).
Визначення
Хроматичне число графу — мінімальне число , таке що множину вершин графу можна розбити на класів , що не перетинаються:
таких, що вершини в кожному класі незалежні, тобто будь-яке ребро графу не з'єднує вершини одного й того ж класу.
Пов'язані визначення
- K-розфарбовний граф — граф, хроматичне число якого не перевищує . Тобто його вершини можна розфарбувати різними кольорами так, що кінці будь-якого ребра будуть різних кольорів.
- K-хроматичний граф — граф, хроматичне число якого дорівнює .
Реброве розфарбування
Хроматичний клас графу G — мінімальна кількість кольорів , в які можна розфарбувати ребра графу G так, щоб суміжні ребра були різних кольорів. Позначається χ'(G). Проблема ребрового розфарбування довільного плаского кубічного графу без мостів трьома кольорами еквівалентна відомій Проблемі чотирьох фарб. Реброве розфарбування визначає 1-факторизацію графу.
Хроматичний многочлен
Якщо розглядати кількість відмінних розфарбувань позначеного графу як функцію від доступної кількості кольорів t, то з'ясується, що ця функція завжди буде поліномом від t. Цей факт був виявлений Біркгофом і Д. С. Люїсом-мол.[1] при спробі довести гіпотезу чотирьох фарб.
Розглянемо граф, зображений на малюнку. Використовуючи лише три кольори, існує 12 варіантів розфарбування. З двома кольорами його взагалі не можна розфарбувати. З чотирма, він може бути розфарбований у 24 + 4*12 = 72 спосіб: використання всіх чотирьох дає 4! = 24 правильних розфарбувань; і для кожного вибору 3-х з 4-х доступних кольорів маємо 12 варіантів. Таким чином, таблиця кількості правильних розфарбувань виглядає таким чином:
Доступно кольорів | 1 | 2 | 3 | 4 | … |
Кількість розфарбувань | 0 | 0 | 12 | 72 | … |
Хроматичний многочлен — функція P(G, t), яка рахує кількість t-розфарбувань G. Для графу з малюнка P(G, t) = t(t − 1)2(t − 2), і насправді, P(G, 4) = 72.
Трикутник | |
Повний граф | |
Дерево с вершинами | |
Цикл | |
Граф Петерсена |
Узагальнення
Також хроматичне число можна розглядати для інших об'єктів, наприклад, для метричних просторів. Так хроматичним числом площини називається мінімальне число χ таке, що існує розфарбування всіх точок площини в один із χ кольорів і при цьому ніякі дві точки одного кольору не розташовані на відстані 1 одна від одної (площина не містить монохроматичних відрізків довжини 1). Аналогічно для простору будь-якої розмірності.
Значення для теорії графів
Багато глибоких задач теорії графів легко формулюються в термінах розфарбовування. Найвідоміша з-посеред таких задач, проблема чотирьох фарб, на сьогодні розв'язана, однак з'являються нові, наприклад, узагальнення проблеми чотирьох фарб, гіпотеза Хадвігера.
Див. також
Примітки
- Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.