Satz von Brooks
Der Satz von Brooks gibt eine Obergrenze für die Anzahl der Farben an, die benötigt werden, um alle Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben.
Vollständige Graphen benötigen eine weitere Farbe als ihr maximaler Grad.
Aussage
Die Knotenfärbungszahl eines zusammenhängenden Graphen, der weder vollständig noch ein Kreis ungerader Länge ist, ist höchstens so hoch wie der Maximalgrad des Graphen.
Zusatz: Ist der Graph vollständig oder ein Kreis ungerader Länge, so benötigt man Maximalgrad + 1 Farben.
Literatur
- Reinhard Diestel: Graphentheorie. 3. Auflage. Springer-Verlag, Heidelberg 2006, ISBN 3-540-21391-0, S. 125.
Weblinks
- Eric W. Weisstein: Brooks' Theorem. In: MathWorld (englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.