3.1 Теорема об оптимальной раскраске

Теорема об оптимальной раскраске звучит так: «Если граф G является r-хроматическим, то он может быть раскрашен с использованием r (или меньшего числа) красок с помощью следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество S(G), затем окрашивается в следующий цвет множество S(X\S(G)) и так далее до тех пор, пока не будут раскрашены все вершины».

Доказательство теоремы. Тот факт, что такая раскраска, использующая только r цветов, всегда существует, может быть установлен следующим образом. Пусть существует раскраска в r цветов, такая, что одно или больше множеств, окрашенных в один и тот же цвет, не являются максимальными независимыми множествами в смысле, упомянутом выше. Перенумеруем цвета произвольным способом. Очевидно, что мы можем всегда покрасить в цвет 1 те вершины (пусть это множество V_i′), которые не были окрашены в этот цвет и которые образуют максимальное независимое множество вместе с множеством V_i всех вершин графа, уже окрашенных в цвет 1. Эта новая раскраска возможна потому, что никакая вершина из множества V_i′ не является смежной ни с какой вершиной из V_i′ и, следовательно, всякая вершина, которая смежна хотя бы с одной вершиной из V_i′, окрашена в цвет, отличный от цвета 1, и поэтому не затрагивается процедурой перемены цвета вершин из V_i′. Рассматривая теперь подграф (X − V_i′) и проводя с ним аналогичные манипуляции, мы окрасим в цвет 2 какое-то (новое) максимальное независимое множество и т. д.

С помощью процедуры, описанной в этой теореме можно получить раскраску с минимальным количеством цветов для данного графа. Такая раскраска называется оптимальной независимой раскраской.