Задача о раскраске вершин графа. Можно ли вершины неориентированного графа раскрасить в k цветов, так, чтобы соседние вершины имели разные цвета?

Частный случай Vertex coloring для 3х цветов.

•  ?
• Что будет сертификатом?

Cертификат → собственно раскраска.

• 3ESAT
• m дизъюнкций
• n переменных.

• Три вершины → метки 0, 1, 2. → треугольник «a»
• Для каждого литерала по вершине → 2n → «б» → лепестки из узла «2»
• Для каждой дизъюнкции → 7 вершин → 7m → «в»
  • , , ← литералы из скобки
• Итого → 3 + 2n + 7m вершин.