Определение: Граф G с хроматическим числом χ(G)=2 называется бихроматическим.

Теорема: Граф G двудолен ⇔ G есть бихроматический граф.

Необходимость⇒: пусть G = (V1,V2,E) есть двудольный граф. Вершины из V1 окрасим в один цвет, а вершины из V2 в другой. Полученная раскраска вершин – правильна, ибо соседние раскрашенные вершины, одна из V1, другая из V2, окрашена в разные цвета. Следовательно, граф есть бихроматический.
⇐Достаточность: Пусть G есть бихроматический граф, тогда множество его вершин можно разбить на два класса:
V1 – вершины из G, окрашенные в один цвет.
V2 – вершины из G, окрашенные в другой цвет.

Ребра из G могут соединять вершины только из различных классов ⇒ граф G = (V1,V2,E) – двудолен.

Замечание: Следующие утверждения эквивалентны:
1) Граф G бихроматический.
2) Граф G двудолен.
3) Все простые циклы в G имеют четную длину.

Дерево есть бихроматичный граф, ибо вершины четных ярусов графа можно раскрасить в один цвет, а нечетных ярусов в другой.

Утверждение: Пусть Kp есть полный граф с p вершинами, тогда χ(K_p) = p.

Доказательство: Индукцией по p.
Базис: p=3 (треугольник), χ(K₃)= 3.
Предположений индукции: предположим, что χ(K_p-1) = p-1 красок.
Шаг: Покажем, что χ(K_p) = p. В самом деле, пусть v есть некоторая вершина в Kp. Удалим вершину v из Kp вместе c принадлежащими ей ребрами. Тогда граф K_p – v = K_p-1 p-1-раскрашиваем по предположению индукции p-1 красками. 1,2,3…p-1. Вершина v в Kp может быть раскрашиваема только новой краской p. Поэтому χ(K_p) = p. Шаг индукции установлен. Утверждение:доказано.

Следствие: Существует граф со сколь угодно большим хроматическим числом (полные графы).

Следствие: Существует граф со сколь угодно малым хроматическим числом (пустые графы).

Комментарии запрещены.