ГРАФА РАСКРАСКА

ГРАФА РАСКРАСКА - приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. просто раскраской графа. Граф наз. k-pаскрашиваемым, если существует правильная вершинная Г. р. к цветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. хроматическим числом χ(G) графа G. Если χ(G) = k, то граф G наз. k-хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа G равна r, то граф G всегда r-раскрашиваем, за исключением двух случаев: 1) r = 2 и G имеет компоненту связности, являющуюся циклом нечетной длины; 2) r > 2 и полный граф с r + 1 вершинами является компонентой связности графа G.

Для объединения двух графов G₁ и G₂ справедливо неравенство

χ(G₁ ∪ G₂) ≤ χ(G₁)χ(G₂),

причем равенство здесь достигается. Более того, если граф G такой, что χ(G) = k = ab, то найдутся подграфы G₁ и G₂ в G такие, что G = G₁ ∪ G₂, χ(G₁) = a, χ(G₂) = b. Если G - граф с n вершинами и G̅ - граф, дополнительный к G, то

причем все границы достигаются. Хроматическим числом χ(S) двумерной поверхности S наз. максимум хроматич. чисел графов, допускающих правильную укладку на S (см. Графа укладка). Для ориентируемой поверхности S_γ рода γ > 0 справедливо равенство

При γ = 0 это равенство принимает вид χ(S₀) = 4, что составляет утверждение четырех красок задачи. Пусть f(G, t) - число различных правильных раскрасок графа G с нумерованными вершинами в t или меньше цветов, тогда для любого графа G функция f(G, t) есть многочлен от переменной t, наз. хроматическим многочленом графа G. Напр., хроматич. многочлен любого дерева с n вершинами имеет вид f(G, t) = t(t - 1)^n-1. Реберное хроматич. число (хроматический класс) χ'(G) графа G - это наименьшее число цветов, достаточное для правильной раскраски ребер графа G. Если максимальная степень вершин графа G равна k (допускаются кратные ребра), то

k ≤ χ'(G) ≤ [3k/2].

Если при этом кратность каждого ребра не более r, то χ'(G) ≤ k + r. В частности, для графов без петель и кратных ребер k ≤ χ'(G) ≤ k + 1.

Задачи на Г. р. возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента и других областях.

Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Оре О., Теория графов, пер. с англ., М., 1968; [3] Шеннон К. Э., «Кибернетический сборник», 1960, в. 2, с. 249-53.

В. Б. Алексеев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.