×

zbMATH — the first resource for mathematics

Graph theory and probability. (English) Zbl 0084.39602
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)>l^{1+1/2k}; \qquad f(k,l)> {k+1-2 \choose k-1}^{c_1}; \qquad h(2k+1,l)<c_2^{l_1+1/k} \] und ohne hier ausgeführten Beweis: \(f(3,l)=h(3,l)>l^{2-\varepsilon}\); \(h(k,l)>c_3^{l_1+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

MSC:
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
Keywords:
topology
PDF BibTeX XML Cite
Full Text: DOI