Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 144.45401
Autor: Erdös, Pál
Title: On the construction of certain graphs (In English)
Source: J. Comb. Theory 1, 149-153 (1966).
Review: Es bezeichne G = G(n) einen Graphen mit n Punkten. Turán (Zbl 055.17004) bestimmte die Maximalzahl f(n) der Kanten eines Graphen G(n), der kein Dreieck (als Teilgraphen) enthält, als f(n) = [ 1/4 n2]. Ist I(G) die Kardinalzahl der größten unabhängigen Punktmenge des Graphen G (unabhängig heißt, daß keine zwei Punkte durch eine Kante verbunden sind), so gilt für den (eindeutig bestimmten) Turánschen Extremalgraphen Gex: I(Gex = [ 1/2 (n+1)]. B.Andrásfai (Zbl 125.11802) verschärfte das Turánsche Problem durch die zweite Bedingung: I(G) \leq u mit u \leq I(Gex) und löste es für u \geq [2n/5].
Für die Andrásfaische Maximalzahl f(n,u) gilt generell (^*) f(n,u) \leq 1/2 un. Der erste Teil der vorliegenen Arbeit ist der Konstruktion von Graphen gewidmet, welche die Andrásfaischen Bedingungen erfüllen und für die in (^*) das Gleichheitszeichen gilt. (Das sind genau die Graphen, bei denen die Menge der Nachbarpunkte jedes beliebigen Punktes eine größte unabhängige Punktmenge mit u Punkten ist.) Für u \geq [2n/5] wurden diese Graphen vollständig von Andrásfai (loc. cit.) angegeben. Mit Hilfe eines Satzes von D.J.Kleitman (Zbl 141.00801) konstruiert der Verf. in vorliegender Arbeit derartige Graphen für u = I(G) = n1-c+c(1), wo n\equiv 1(mod 3), 4c = 32/27. Unter der Voraussetzung, daß eine Vermutung von Czipszer und dem Verf. richtig ist, konstruiert der Verf. im zweiten Teil der Arbeit für jede unendliche Kardinalzahl m Beispiele von m-chromatischen dreiecksfreien Graphen mit m Punkten. Die Existenz solcher Graphen wurde vom Verf. und R.Rado (Zbl 097.16402) bewiesen.
Vermutungen, Problemstellungen (und Druckfehler) würzen die Arbeit.
Reviewer: W.Wessel (Berlin)
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag