Chromatische Zahl

Die chromatische Zahl $\chi (G)$ (auch Knotenfärbungszahl oder kurz Färbungszahl, selten auch Farbzahl genannt) eines Graphen ist die kleinste Zahl $k$, für die der Graph eine zulässige Knotenfärbung mit $k$ Farben besitzt. (Eine Färbung heißt zulässig oder gültig, wenn es keine benachbarten Knoten gibt, die mit der gleichen Farbe gefärbt sind.) Die chromatische Zahl ist zugleich die kleinste natürliche Zahl λ, für die das chromatische Polynom $\chi (G,\lambda )\neq 0$ ist.

Die achromatische Zahl $\psi (G)$ eines Graphen $G$ ist die größte Zahl $k$, für die $G$ eine gültige und vollständige Knotenfärbung mit $k$ Farben hat. (Eine Färbung heißt vollständig, wenn es zu jedem Paar von verschiedenen Farben eine Kante gibt, deren Endknoten mit diesen beiden Farben gefärbt sind.)

Die pseudo-achromatische Zahl $\psi _{s}(G)$ eines Graphen $G$ ist die größte Zahl $k$, für die $G$ eine vollständige Knotenfärbung hat. Im Gegensatz zur achromatischen Zahl ist hier nicht die Gültigkeit der Färbung verlangt.

Siehe auch

• Chromatischer Index (Kantenfärbungszahl)