3-COL

3-Färbbarkeit: Ein Graph $G$ ist 3-färbbar, wenn es eine Funktion $c : V (G) \to {C_{1}, C_{2}, C_{3}}$ gibt, so dass $c (u) \neq c (v)$ für alle Kanten ${u, v} \in E (G)$ .
3-COL Problem: Das Entscheidungsproblem, ob ein gegebener Graph $G$ 3-färbbar ist. Dieses Problem ist NP-vollständig.