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.^[1]

Formulierung des Satzes

Der Satz lautet wie folgt:^[2][3][4][5]

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

(1)   ${\displaystyle 2\cdot {\sqrt {p}}\leq \chi (G)+\chi ({\overline {G}})\leq p+1}$

(2)   ${\displaystyle p\leq \chi (G)\cdot \chi ({\overline {G}})\leq {\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:^[2][4]

Zu (1)

1. Die untere Schranke nehmen (etwa) der vollständige Graph ${\displaystyle K_{1}}$ oder auch der Kreisgraph ${\displaystyle C_{4}}$ an.
2. Die obere Schranke nehmen lediglich die vollständigen Graphen ${\displaystyle K_{p}}$ und deren Komplementärgraphen ${\displaystyle {\overline {K_{p}}}}$ sowie die Kreisgraphen ${\displaystyle C_{p}}$ an.

Zu (2)

1. Die untere Schranke nehmen (etwa) alle ${\displaystyle K_{p}}$ an.
2. Die obere Schranke nehmen lediglich ${\displaystyle K_{1}}$ , ${\displaystyle K_{2}}$ , ${\displaystyle {\overline {K_{2}}}}$ sowie ${\displaystyle C_{5}}$ an.

Literatur

Originalarbeiten

• H.-J. Finck: Über die chromatischen Zahlen eines Graphen und seines Komplements. I, II. In: Wissenschaftliche Zeitschrift der Technischen Hochschule Ilmenau. Band 12, 1966, S. 243–246.  MR0214508
• E. A. Nordhaus, J. W. Gaddum: On complementary graphs. In: Amer. Math. Monthly. Band 63, 1956, S. 175–177, doi:10.2307/2306658.  MR0078685

Übersichtsarbeiten

• M. Aouchiche, P. Hansen: A survey of Nordhaus–Gaddum type relations. In: Discrete Applied Mathematics. Band 161, 2013, S. 466–546, doi:10.1016/j.dam.2011.12.018. 

Monographien

• Michael Capobianco, John C. Molluzzo: Examples and Counterexamples in Graph Theory. North-Holland, New York, Amsterdam, Oxford 1978, ISBN 0-444-00255-3.  MR0491272
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4.  MR0282850
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 

Einzelnachweise und Fußnoten

1. ↑ Siehe etwa M. Aouchiche, P. Hansen: A survey of Nordhaus–Gaddum type relations. In: Discrete Appl. Math. 161 (2013), 466–546.
2. ↑ ^{a b} Michael Capobianco, John C. Molluzzo: Examples and Counterexamples in Graph Theory. 1978, S. 5
3. ↑ Frank Harary: Grapentheorie. 1974, S. 137–138
4. ↑ ^{a b} Rudolf Halin: Graphentheorie I. 1980, S. 250 ff., 253–254
5. ↑ Klaus Wagner: Graphentheorie. 1970, S. 129 ff., 137