notes/school/di-ma/20181204_1-kantenfaerbung.md

title	date
Kantenfärbung	2018-12-04

Beispiel: n Teams \widehat{=} Knoten, m Partien zwischen je 2 Teams \widehat{=} Kanten

Festlegen der Termine, an denen die SPiele stattfinden (Termine haben Nummern 1,...,k).

Frage: Wie viele Termine braucht man?

Bedingung: Kein Team kann an einem Termin 2 Spiele spielen

Definition (Kantenfärbung)

Sei G=(V,E) ein Graph.

i) Eine Kantenfärbung ist eine Abbildung $$ c : E \rightarrow {1,...,k} $$ mit der Eigenschaft $$ \forall e,e' \in E, e \neq e' \land e \cap e' = \emptyset : c(e) \neq c(e')

i) Ein Graph heißt $k$-kantenfärbbar, falls es eine $k$-Kantenfärbung für $G$ gibt.

i) Der chromatische Index \chi'(G) ist definiert als $$ \chi'(G) = \min {k \in \mathbb{N} \mid G \text{ ist } k \text{-kantenfärbbar}}

Bemerkung: Es gilt \chi'(G) \geq \Delta(G) mit $\Delta(G) = \max\limits_{v \in V} deg(v)$, da alle \Delta(G) Kanten eines Knotens v mit deg(v) = \Delta(G) unterschiedliche Farben haben müssen.

Es gilt sogar:

Satz

Sei G=(V,E) Graph, dann gilt

\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1

ohne Beweis

\tag*{$\Box$}

Bemerkung: zu entscheiden, ob \chi'(G) = \Delta(G) oder \chi'(G)=\Delta(G)+1 ist im Allgemeinen ein schweres Problem.