NP-полнота задачи о раскраске графа

Формулировка задачи

Даны граф [math] G = \lt V, E\gt [/math] и число [math] k [/math]. Нужно проверить, правда ли, что можно раскрасить вершины графа в [math] k [/math] цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.

Утверждение

Сформулированная выше задача NP-полна.

Доказательство

Доказательство принадлежности задачи классу NP

Сертификатом для решения данной задачи будет последовательность [math] \{c_i\}_ {i=1}^{n}[/math], где [math] n = |V| [/math], а [math] c_i [/math] обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке [math] [1, k] [/math].

Доказательство принадлежности задачи классу NPH

Сведем задачу 3CNFSAT к данной.
Пусть дана [math] \varphi = (a_1 \lor b_1 \lor c_1) \land (a_2 \lor b_2 \lor c_2) \land ... \land (a_m \lor b_m \lor c_m) [/math], где [math]a_i[/math], [math]b_i[/math] и [math]c_i[/math] - переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать [math] \{x_i\}_{i=1}^n [/math].