Раскрашиваемость графа

[Антон Жернов]

Здравствуйте!

Существует ли критерий раскрашиваемости в k цветов графа, заданнного матрицей смежности? Возможно ли в принципе написать предикат для произвольного k?

Подскажите, пожалуйста, где можно почитать про критерии раскрашиваемости?
Заранее спасибо.