k-Färbung

Eine $k$-Färbung von $G$ ist eine Abbildung
$c:V(G)\to \{1,...,k\}$,
die jedem Knoten von $G$ eine von $k$ möglichen Farben so zuordnet,
dass $c(a)\ne c(b)$ für alle Kanten $\{a,b\}\in E(G)\mathrm{\setminus }E(T)$ gilt.

Links

• DS_vollständiger_foliensatz.pdf