Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 084.39602
Autor: Erdös, Pál
Title: Graph theory and probability. (In English)
Source: Can. J. Math. 11, 34-38 (1959).
Review: Punkte eines Graphen G heißen in G unabhängig, wenn keine zwei von ihnen durch eine Kante verbunden sind. h (k,l) sei die kleinste Zahl von der Eigenschaft, daß jeder Graph mit h(k,l) Punkten entweder einen geschlossenen Kantenzug von k oder weniger Kanten, oder l unabhängige Punkte hat. f(k,l) sei die kleinste Zahl der Eigenschaft, daß jeder Graph mit f(k,l) Punkten entweder einen vollständigen Graph mit k Punkten oder l unabhängige Punkte enthält. Durch Wahrscheinlichkeitsrechnungen ergibt sich hier bei genügend großem l: h(k,l) > l1+1/2k; f(k,l) > {k+1-2 \choose k-1}c1; h(2k+1,l) < c2l1+1/k und ohne hier ausgeführten Beweis: f(3,l) = h(3,l) > l2-\epsilon; h(k,l) > c3l1+1/3k. Aus der ersten dieser fünf Ungleichungenfolgt, daß es für jedes r und k r-chromatische Graphen gibt, die kein m-Eck enthalten mit m \leq k.
Reviewer: H.Künneth
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag