Definition
Die kleinste ganze Zahl k, so dass die Knoten eines Graphen mit k Farben so gefärbt werden können, dass keine zwei benachbarten Knoten dieselbe Farbe haben (eine echte Knotenfärbung).
Prinzip
Prinzip
Die chromatische Zahl misst, wie ein Graph in unabhängige Mengen partitioniert werden kann: sie ist die minimale Anzahl von Farbklassen, sodass jede Klasse eine unabhängige Menge ist.
Demonstration
Demonstration
Ein vollständiger Graph mit n Knoten hat chromatische Zahl n. Jeder bipartite Graph mit mindestens einer Kante hat chromatische Zahl 2. Ein ungerader Kreis C_{2m+1} hat chromatische Zahl 3.
Fehlanwendung
Fehlanwendung
Die chromatische Zahl der Knoten mit dem chromatischen Index (Kantenfärbung), der fraktionalen oder der Listenchromatik verwechseln, oder annehmen, dass triviale Schranken (z. B. χ ≤ Δ+1) stets Gleichheiten sind, ohne Ausnahmen (Brooks' Theorem) zu prüfen.
Konsequenz
Konsequenz
Die chromatische Zahl begrenzt Färbungen in Einsatzplanungs- und Registerallokationsproblemen, gibt Auskunft über Cliquenstruktur (Clique-Zahl ist untere Schranke) und ist rechnerisch schwer zu bestimmen (NP-schwer für k≥3).
Umkehrung
Umkehrung
Die Umkehr wäre die Zulassung nicht-echter Färbungen, die gleiche Farben an benachbarten Knoten erlauben und so die benötigte Farbanzahl reduzieren; Clique-Überdeckungsgrößen oder die Unabhängigkeitszahl sind alternative Partitionierungsmaße.
Abgrenzung
Abgrenzung
Definiert für endliche und unendliche Graphen (wobei die chromatische Zahl unendlich sein kann); für gerichtete Graphen und Hypergraphen weichen die entsprechenden Begriffe ab und benötigen angepasste Definitionen (orientierte chromatische Zahl, Hypergraph-Färbung).
Semantische Spannung
Semantische Spannung
Spannung zwischen chromatischer Zahl und Clique-Zahl (untere Schranke), chromatischem Polynom (zählt Färbungen) sowie fraktionaler und Listenchromatik, die Definitionen verfeinern oder lockern und von χ abweichen können.
Synthese
Synthese
Die chromatische Zahl ist die minimale Anzahl unabhängiger Knotengruppen, die für eine echte Färbung nötig sind; sie erfasst die kombinatorische Komplexität eines Graphen und steht in Beziehung zu Cliquen, Graden und Färbungsvarianten.