Theorem from Nordhaus-Gaddum

The set of Nordhaus-Gaddum is a theorem from the mathematical branch of graph theory , which is based on a work of the mathematician Edward Alfred Nordhaus and Jerry W. Gaddum back from the year 1956th The theorem formulates four basic inequalities about the relationship between the chromatic number of a graph , the chromatic number of the associated complementary graph and the number of nodes . It initiated a number of follow-up work.

Formulation of the sentence

The sentence is as follows:

For a finite simple graph with nodes and its complementary graphs , the following inequalities always apply: ${\displaystyle G=(V,E)}$ ${\displaystyle p}$ ${\displaystyle (p\in \mathbb {N} )}$ ${\displaystyle {\overline {G}}=(V,{\binom {V}{2}}\setminus E)}$

(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}}}$

Borderline cases

In a work from 1966, the mathematician Hans-Joachim Finck took up the question of which graphs in the above inequalities the lower or upper bounds are assumed for, i.e. equality applies. In summary, the following results:

To 1)

1. The lower bound is assumed by (roughly) the complete graph or the circular graph . ${\displaystyle K_{1}}$ ${\displaystyle C_{4}}$
2. Only the complete graphs and their complementary graphs as well as the circular graphs assume the upper bound . ${\displaystyle K_{p}}$ ${\displaystyle {\overline {K_{p}}}}$ ${\displaystyle C_{p}}$

To (2)

1. (Roughly) everyone accepts the lower bound . ${\displaystyle K_{p}}$
2. The upper bound only accept , , and on. ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$ ${\displaystyle {\overline {K_{2}}}}$ ${\displaystyle C_{5}}$

literature

Original work

• EA Nordhaus, JW Gaddum: On complementary graphs . In: Amer. Math. Monthly . tape 63 , 1956, pp. 175-177 , doi : 10.2307 / 2306659 . MR0078685
• H.-J. Finck: About the chromatic numbers of a graph and its complement. I, II. In: Scientific journal of the Technical University of Ilmenau . tape 12 , 1966, pp. 243-246 . MR0214508

Monographs

• Michael Capobianco , John C. Molluzzo : Examples and Counterexamples in Graph Theory . North-Holland , New York, Amsterdam, Oxford 1978, ISBN 0-444-00255-3 . MR0491272
• Frank Harary : Graph Theory . R. Oldenbourg Verlag , Munich, Vienna 1974, ISBN 3-486-34191-X .
• Rudolf Halin : Graph Theory I (=  yields of research . Volume 138 ). Scientific Book Society , Darmstadt 1980, ISBN 3-534-06767-3 . MR0586234
• Klaus Wagner : Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut , Mannheim (inter alia) 1970, ISBN 3-411-00248-4 . MR0282850

References and footnotes

1. ↑ See for example the list in MathSciNet  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. !  
2. ↑ ^{a b} Michael Capobianco, John C. Molluzzo: Examples and Counterexamples in Graph Theory. 1978, p. 5
3. ^ Frank Harary: Grape theory. 1974, pp. 137-138
4. ↑ ^{a b} Rudolf Halin: Graphentheorie I. 1980, pp. 250 ff., 253-254
5. ^ Klaus Wagner: Graph theory. 1970, p. 129 ff., 137