для любых различных смежных вершин V1 и V2 выполняется фи(V1)не равно фи(V2)
T-хроматический, если он обладает t раскраской, но не обладает t-1 раскраской. t- хроматическое число X(G)
Теорема: граф является бихроматическим тогда и только тогда, когда в нем отсутствуют циклы нечетной длины
Следствие: любое ненулевое дерево является бихроматическим графом
Теорема: любой планарный граф можно раскрасить пятью красками
области применения раскраски графов: составление расписания, задача распределения оборудования, задание адресов информационных каналов, судоку.
