Задача о раскраске вершин графа. Можно ли вершины неориентированного графа раскрасить в k цветов, так, чтобы соседние вершины имели разные цвета?
Частный случай Vertex coloring для 3х цветов.
Cертификат → собственно раскраска.