0 Daumen
437 Aufrufe

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

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community