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 (G) ist das kleinste k,
für das G eine konfliktfreie k-Färbung besitzt.
formal:
- Farben
Fk = {1, 2,..., k}, eine k-Färbung
c : V(G)Fk
-
xy E : c(x) c(y)
-
(G) = min{k | konfliktfreie $k$-Färbung $c$ für $G$}
Johannes Waldmann
2005-01-25