Chromatischer Index

Graph-Eigenschaft
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 20. Februar 2003 um 13:32 Uhr durch JakobVoss (Diskussion | Beiträge) (neu (Definition und Verweis)). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Der chromatische Index (auch Kantenfärbungszahl) ist in der Graphentheorie die kleinste Anzahl von Farben, mit der sich die Kanten eines Graphen färben lassen, ohne dass zwei an einem Knoten anliegenden Kanten die selbe Farbe bekommen. Der chromatische Index eines Graphen entspricht entweder seinem Maximalgrad oder ist um eins höher als dieser. Trotzdem ist das Problem, den chromatischen Index eines beliegen Graphen zu bestimmen, NP-schwer. In bipartiten Graphen entspricht der chromatische Index dem Maximalgrad.

Näheres unter Färbung von Graphen.