Satz von Nordhaus-Gaddum

Der Satz von Nordhaus-Gaddum ist ein Lehrsatz aus dem mathematischen Teilgebiet der Graphentheorie, welcher auf eine Arbeit der beiden Mathematiker Edward Alfred Nordhaus und Jerry W. Gaddum aus dem Jahre 1956 zurückgeht. Der Satz formuliert vier grundlegende Ungleichungen über den Zusammenhang zwischen der chromatischen Zahl eines Graphen, der chromatischen Zahl des zugehörigen Komplementärgraphen und der Knotenzahl. Er war Anstoß für eine Anzahl von Folgearbeiten.

Formulierung des Satzes

Der Satz lautet wie folgt:

Für einen endlichen schlichten Graphen $G=(V,E)$ mit $p$ Knoten $(p\in \mathbb{N})$ und seinen Komplementärgraphen $\bar{G}=(V,(\genfrac{}{}{0ex}{}{V}{2})\setminus E)$ gelten stets folgende Ungleichungen:

(1)   $2\cdot \sqrt{p}\le \chi (G)+\chi (\bar{G})\le p+1$

(2)   $p\le \chi (G)\cdot \chi (\bar{G})\le \frac{(p+1{)}^2}{4}$

Grenzfälle

In einer Arbeit von 1966 hat sich der Mathematiker Hans-Joachim Finck die Frage aufgegriffen, für welche Graphen in den obigen Ungleichungen die unteren bzw. oberen Schranken angenommen werden, also die Gleichheit gilt. Es ergibt sich zusammengefasst Folgendes:

Zu (1)

1. Die untere Schranke nehmen (etwa) der vollständige Graph $K_1$ oder auch der Kreisgraph $C_4$ an.
2. Die obere Schranke nehmen lediglich die vollständigen Graphen $K_p$ und deren Komplementärgraphen $\overline{K_p}$ sowie die Kreisgraphen $C_p$ an.

Zu (2)

1. Die untere Schranke nehmen (etwa) alle $K_p$ an.
2. Die obere Schranke nehmen lediglich $K_1$ , $K_2$ , $\overline{K_2}$ sowie $C_5$ an.

Literatur

Originalarbeiten

• Vorlage:Literatur MR0078685
• Vorlage:Literatur MR0214508

Übersichtsarbeiten

• Vorlage:Literatur

Monographien

• Vorlage:Literatur MR0491272
• Vorlage:Literatur
• Vorlage:Literatur MR0586234
• Vorlage:Literatur MR0282850