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

Нехай р – деяке натуральне число.

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

Визначення. Найменше число р, при якому граф є р-хроматичним, називається хроматичним числом графу і позначається ¡(G).

Якщо ¡(G) = 2, то граф називається біхроматичним. Необхідною і достатньою умовою біхроматичності графу є відсутність у ньому циклів непарної довжини. Визначення хроматичного числа графу, за винятком біхроматичного графу, є трудомісткою задачею.

Приклад. Для розфарбування лівого графу (рис. 17.3) необхідно три кольори, для розфарбування правого – два кольори, тобто правий граф – біхроматичний.

Рис. 17.3. Небіхроматичний і біхроматичний графи