ich habe folgendes Problem.
Ich möchte zeigen, dass die Chromatische Zahl in einem k-regulären Graphen
G = (V,E) durch die folgende Formel gegeben ist:
⌈ |V| / (|V| - k) ⌉
Die chromatische Zahl ist die Anzahl der Farben, die benötigt werden um einen Graphen zu färben.
k regulär bedeutet, dass alle Knoten den Grad k haben wobei k nicht größer als die Knotenanzahl sein kann.
Ich habe mir das Problem schon an verschiedenen Beispielen veranschaulicht, aber habe keinen Ansatz wie ich davon die Allgemeine Gültigkeit zeigen kann.
Danke schon mal im voraus