k-Färbung

Einfache Sprache

Eine k-Färbung $f$ färbt die Knoten eines Graphen mit $k$ Farben so, dass nur Kanten zwischen unterschiedlich gefärbten Knoten exisitert.

Def. k-Färbung

Eine k-Färbung eines Ungerichteter Graph $G=(V,E)$ ist eine Funktion $f:V\to \{1,\ldots,k\}$ mit $f(i)\not=f(j)$ für alle $\{i,j\}\in E$ mit $i\not=j$.