Graph/Färbungen/Einführung/Textabschnitt

Beispiel

In einer Firma arbeiten verschiedene Personen, von denen manche sich gegenseitig nicht leiden können und daher nicht in einem Team arbeiten sollen. Diese Abneigungen werden durch einen Ausschließungsgraphen visualisiert. Eine Aufteilung in Teams, die diese Abneigungen berücksichtigt, ist eine Abbildung der Knotenpunkte (der Personen) in eine Teammenge mit der Eigenschaft, dass durch eine Abneigungskante verbundene Knotenpunkte auf unterschiedliche Teams abgebildet werden.

Definition

Es sei ${}(V,E)$ ein Graph. Eine Abbildung

$f\colon V\longrightarrow B$

in eine Menge ${}B$ heißt Färbung des Graphen.

Bei ${}f$ denke man an Färbung und bei ${}B$ an bunt. Den Wert ${}f(v)$ nennt man die Farbe von ${}v$ unter der gegebenen Färbung. Es ist keine Einschränkung, nur Farbenmengen der Form ${}\{1,\ldots ,k\}$ zu betrachten.

Diese Definition nimmt keinen Bezug auf die Kantenmenge ${}E$. Dies wird hingegen bei der folgenden Definition entscheidend verlangt.

Definition

Es sei ${}(V,E)$ ein Graph. Eine Färbung

$f\colon V\longrightarrow B$

heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.

Definition

Zu einem Graphen ${}G=(V,E)$ nennt man die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt, die chromatische Zahl des Graphen. Sie wird mit ${}\chi (G)$ bezeichnet.

Lemma

Für die chromatische Zahl ${}\chi (G)$ eines Graphen ${}G=(V,E)$ gelten die folgenden Aussagen.

1. Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ${}\geq 1$ ist.
2. Ein nichtleerer Graph besitzt genau dann die chromatische Zahl ${}1$, wenn er keine Kanten besitzt.
3. Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ${}\leq 2$ ist.
4. Es ist

   ${}\chi (G)\leq {\#\left(V\right)}\,.$

5. Der vollständige Graph ${}K_{n}$ besitzt die chromatische Zahl ${}n$.

Beweis

Siehe Aufgabe.

$\Box$