Erdős, Pál; Rogers, C. A. The construction of certain graphs. (English) Zbl 0194.25304 Can. J. Math. 14, 702-707 (1962). Ein Graph heiße \(k\)-vollständig (\(k\)-unvollständig), wenn er einen (keinen) vollständigen Graphen mit \(k\) Ecken als Teilgraphen enthält. Hauptergebnis der Note ist (vgl. 3. Theorem, S. 704), daß sich zu je zwei natürlichen Zahlen \(k\) und \(l\) \((k \geq 3)\) stets ein Graph \(G\) mit weniger als \(l^{1+c_k}\) Ecken so finden läßt, daß \(G\) \(k\)-unvollständig und jeder von \(l\) Ecken aufgespannte Untergraph von \(G\) \((k-1)\)-vollständig ist. Hierbei können die positiven Konstanten \(c_k\) \((k \geq 3)\) so gewählt werden, daß \(c_k \sim 1/(512 k^4\log k)\) mit \(k \to \infty\) gilt. Der erste Autor hatte in einer früheren Note für \(f(k,l)\) (\(l\) = kleinste natürliche Zahl mit der Eigenschaft, daß für jeden Graphen \(G\) mit \(f(k,l)\) Ecken entweder \(G\) \(k\)-vollständig oder der komplementäre Graph zu \(G\) \(l\)-vollständig ist, vgl. den Satz von Ramsey) die untere Schranke \(l^{1+c_3}<f(3,l) \leq f(k,l)\), \((k \geq 4)\) ermittelt. Aus dem neuen Ergebnis folgt jetzt sogar: \(l^{1+c_k} < h(k,l) \leq f(k,l)\) für \(k \geq 3\), worin \(h(k,l)\) die kleinste natürliche Zahl mit der Eigenschaft bedeutet, daß jeder Graph \(G\) mit \(h(k,l)\) Ecken entweder \(k\)-vollständig ist oder \(l\) Ecken in \(G\) existieren, so daß der von diesen Ecken aufgespannte Untergraph von \(G\) \((k-1)\)-unvollständig ist. Reviewer: K.Wagner Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 4 ReviewsCited in 33 Documents MSC: 05C55 Generalized Ramsey theory 05C35 Extremal problems in graph theory Keywords:topology PDFBibTeX XMLCite \textit{P. Erdős} and \textit{C. A. Rogers}, Can. J. Math. 14, 702--707 (1962; Zbl 0194.25304) Full Text: DOI