Färbungsproblem
Einfache Sprache
Problemstellung:
Gegeben: Ein Ungerichteter Graph $G=(V,E)$ und eine Zahl $k\in\mathbb N_{\geq1}$. Entscheide: Hat $G$ eine k-Färbung?
Satz: Färbungsproblem
CLIQUE ist NP-vollständig.
Beweis Idee: #TODO
- Färbungsproblem $\in NP$
- $\textrm{3-SAT}\preceq$ Färbungsproblem