2015-06-28
414
Нехай р – деяке натуральне число.
Визначення. Граф називається р-хроматичним, якщо його вершини можна розфарбувати “р” різними кольорами так, щоб ніякі дві суміжні вершини не були розфарбовані однаково.
Визначення. Найменше число р, при якому граф є р-хроматичним, називається хроматичним числом графу і позначається ¡(G).
Якщо ¡(G) = 2, то граф називається біхроматичним. Необхідною і достатньою умовою біхроматичності графу є відсутність у ньому циклів непарної довжини. Визначення хроматичного числа графу, за винятком біхроматичного графу, є трудомісткою задачею.
Приклад. Для розфарбування лівого графу (рис. 17.3) необхідно три кольори, для розфарбування правого – два кольори, тобто правий граф – біхроматичний.
Рис. 17.3. Небіхроматичний і біхроматичний графи
