Graphenfärbung

Die Graphenfärbung weist den Elementen eines Graphen Bezeichnungen oder Farben zu, sodass benachbarte Elemente sich unterscheiden, und untersucht die minimale Anzahl der benötigten Farben.

Definition

Eine korrekte Färbung eines Graphen ist eine Zuweisung von Farben zu seinen Knoten, sodass keine zwei benachbarten Knoten dieselbe Farbe haben; die chromatische Zahl ist die geringste Anzahl von Farben, für die eine solche Zuweisung existiert.

Scope

Dieses Thema behandelt die korrekte Knotenfärbung und die chromatische Zahl, die Kantenfärbung und den chromatischen Index, das chromatische Polynom, das die Anzahl der Färbungen zählt, sowie wegweisende Ergebnisse wie den Satz von Brooks, den Satz von Vizing und den Vier-Farben-Satz für planare Graphen. Es verknüpft die Färbung mit Unabhängigkeit, Cliquen und der umfassenderen Theorie der Graphenparameter.

Core questions

• Wie viele Farben werden mindestens benötigt, um einen gegebenen Graphen korrekt zu färben?
• Wie viele korrekte Färbungen mit einer gegebenen Palette lässt ein Graph zu?
• Welche Graphen können mit wenigen Farben gefärbt werden, und welche Hindernisse erzwingen viele?
• Wie erweitern Kantenfärbungen und Listenfärbungen den Grundbegriff?

Key concepts

• Korrekte Knotenfärbung
• Chromatische Zahl
• Chromatisches Polynom
• Kantenfärbung und chromatischer Index
• Satz von Brooks
• Vier-Farben-Satz

Key theories

Vier-Farben-Satz

Jeder planare Graph kann mit höchstens vier Farben korrekt gefärbt werden, eine Aussage, die über ein Jahrhundert lang offen war und 1976 von Appel und Haken mittels umfangreicher computergestützter Fallanalyse erstmals bewiesen wurde.

Satz von Vizing

Die Kanten jedes einfachen Graphen können entweder mit dem maximalen Grad oder mit einem mehr als dem maximalen Grad an Farben korrekt gefärbt werden, wodurch alle Graphen in zwei enge Klassen unterteilt werden.

Clinical relevance

Die Färbung modelliert die konfliktfreie Ressourcenzuweisung: Zeitplanung ohne Kollisionen, Registerzuweisung in Compilern, Frequenzzuweisung in drahtlosen Netzwerken und Sudoku-ähnliche Constraint-Probleme lassen sich alle auf die Graphenfärbung reduzieren.

History

Die 1852 aufgestellte Vier-Farben-Vermutung trieb einen Großteil der Färbungstheorie voran; ihr computergestützter Beweis von Appel und Haken im Jahr 1976 war ein frühes Wahrzeichen der computergestützten Mathematik und löste eine Debatte über die Natur des Beweises aus.

Debates

Status computergestützter Beweise

Die Abhängigkeit des Vier-Farben-Satzes von maschinell überprüften Fällen warf die Frage auf, ob ein Beweis, der für einen Menschen zu lang ist, um ihn von Hand zu überprüfen, als echter mathematischer Beweis gelten sollte.

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

Was ist die chromatische Zahl eines Graphen?

Es ist die kleinste Anzahl von Farben, die benötigt wird, damit benachbarte Knoten immer unterschiedliche Farben erhalten; zum Beispiel hat ein ungerader Zyklus die chromatische Zahl drei.

Gilt der Vier-Farben-Satz für alle Karten?

Er gilt für Karten, die auf der Ebene oder der Kugel gezeichnet sind, wo Regionen verbunden sind; Karten auf Oberflächen wie dem Torus können mehr Farben erfordern.