Выдержка из книги
Кристофайдс Н.N.
Теория графов Алгоритмический подход
Если работу алгоритма не завершать при первом выполнении условия S - X на шаге 4, то алгоритмический процесс будет продолжаться до получения раскраски в г 1 цветов, если такая раскраска существует. Следует отметить, однако, что описанный алгоритм не дает полного перечисления всех возможных раскрасок в г 1 цветов, а только порождает оптимальные независимые раскраски. Такие раскраски могут оказаться только небольшой частью всех возможных раскрасок в г 1 цветов.
