>>四色塗り分けはNP完全

そもそも、NPは判定問題のクラスです。
故に、4彩色可能か?と言う問いを平面グラフ上で
行うと必ずYESになってしまいます。

ゆえに、四色塗り分けはNPに属さない。

しかし、平面上の四色塗り分けの多項式時間アルゴリズムは、
四色定理の証明の系として導くことができます。

ただし、一般のグラフに関して、四色塗り分けはNP困難です。