## [Chromatische Zahl](/de/node/61220) 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.