Выдержка из книги
Ершов А.П.
Введение в теоретическое программирование беседы о методе
Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок, нам надо понять: а нужно ли рассматривать проблему в полной всеобщности. При всей увлеченности очередной интересной математической задачей надо помнить, что в контексте нашего исследования раскраска вершин графа нам нужна не сама по себе, а как средство экономного распределения памяти. Может быть, графы несовместимости, получающиеся для операторных схем, обладают какими-нибудь специальными свойствами, которые могли бы облегчить поиск минимальной раскраски. Например, известно, что любой плоский граф можно раскрасить не более чем пятью красками.