Раскраска графов. Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета

Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета.

Хроматическим числом графа G называется минимальное число цветов, требующееся для раскраски G, и обозначается «xn».

Легко найти хроматические числа некоторых известных графов, например:

, где K(с чертой) – дополнение до полного графа;

K_n – полный граф n вершин;

K_n,m – двудольный граф (в одном множестве n вершин, в другом – m вершин).

Пусть P(G) – наибольшая из степеней вершин графа G, тогда для любого неориентированного графа G выполняется неравенство:

χ(G)<P(G)+1.

Теорема. Для любого связного (n,т)- графа G верны неравенства

, где [...] — целая часть, а {..} — дробная часть числа.

Алгоритм последовательной раскраски:

1) Произвольной вершине х графа G присваивается цвет 1.

2) Если вершины x₁,x₂,…,x_i раскрашены k цветами 1,2,…, k, k<i, то новой произвольно взятой вершине х_i+1 приписывается минимальный цвет, не использованный при раскраске вершин из ее окружения.

Теорема Кенига. Граф двуцветен тогда и только тогда, когда он не содержит нечетных простых циклов.