Knoten-Färbungen

verbal:

• Eine k-Knoten-Färbung eines Graphen ordnet jedem Knoten genau eine der Farben {1, 2,..., k} zu.
• Eine k-Färbung heißt konfliktfrei, wenn jede Kante verschiedenfarbige Knoten verbindet.
• Die chromatische Zahl $\chi$(G) ist das kleinste k, für das G eine konfliktfreie k-Färbung besitzt.

formal:

• Farben F_k = {1, 2,..., k}, eine k-Färbung c : V(G)$\to$F_k
• $\forall$xy $\in$ E : c(x) $\neq$ c(y)
• $\chi$(G) = min{k | $\exists$konfliktfreie $k$-Färbung $c$ für $G$}