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.Siehe etwa M. Aouchiche, P. Hansen: A survey of Nordhaus–Gaddum type relations. In: Discrete Appl. Math. 161 (2013), 466–546.
Formulierung des Satzes Der Satz lautet wie folgt:Michael Capobianco, John C. Molluzzo: Examples and Counterexamples in Graph Theory. 1978, S. 5Frank Harary: Grapentheorie. 1974, S. 137–138Rudolf Halin: Graphentheorie I. 1980, S. 250 ff., 253–254Klaus Wagner: Graphentheorie. 1970, S. 129 ff., 137 Für einen endlichen schlichten Graphen mit Knoten und seinen Komplementärgraphen gelten stets folgende Ungleichungen: (1) (2)
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) Die untere Schranke nehmen (etwa) der vollständige Graph oder auch der Kreisgraph an. Die obere Schranke nehmen lediglich die vollständigen Graphen und deren Komplementärgraphen sowie die Kreisgraphen an.
Zu (2) Die untere Schranke nehmen (etwa) alle an. Die obere Schranke nehmen lediglich , , sowie an.
Literatur Originalarbeiten MR0078685 MR0214508 Übersichtsarbeiten
Monographien MR0491272
MR0586234 MR0282850
Einzelnachweise und Fußnoten
Kategorie:Graphentheorie Nordhaus-Gaddum, Satz von Nordhaus-Gaddum, Satz von