Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 161.43306
Autor: Erdös, Pál
Title: On some new inequalities concerning extremal properties of graphs (In English)
Source: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 77-81 (1968).
Review: [For the entire collection see Zbl 155.00201.]
Die vorliegende Arbeit schließt sich an den von P. Turán stammenden Problemenkreis an: es wird die kleinste ganze Zahl f(n; G) gesucht derart, daß sämtliche n Punkte und f(n; G) Kanten besitzende Graphen den Graphen G als Teilgraphen enthalten; ferner wird nach der Struktur eines zu einem Graphen G gehörigen extremen Graphen gefragt, worunter man jene n Punkte und f(n; G)-1 Kanten besitzenden Graphen versteht, die G nicht als Teilgraphen enthalten. Bekanntlich wurde dieses Problem von P. Turán für den Fall gelöst, daß G ein vollständiger r-Graph ist (bei beliebigem r); oder in anderer Fassung, daß G ein vollständiger r-Graph ist (bei beliebigem r); oder in anderer Fassung, daß G ein r Punkte besitzender r-chromatischer Graph Kr ist. Es ergab sich (mit der Bezeichnung Kr(p1,...,pr) für vollständige r-chromatische Graphen, wobei pi Punkte die i-te Farbe besitzen, und je zwei verschieden gefärbte Punkte verbunden sind), daß die zu Kr = Kr(1,...,1) gehörigen extremen Graphen alle die Struktur Kr-1(p1,...,pr-1) haben, wobei die Zahlen pi so wenig wie möglich von einander abweichen. Das Hauptergebnis vorliegender Arbeit (Satz 3) legt dar, daß die zu G gehörigen extremen Graphen auch dann von ähnlicher Struktur sind (mit Abweichungen infolge der Abhängigkeit von n), wenn G bei beliebigem n ein n Punkte besitzender r-chromatischer Graph ist. Im Beweis wird eine auch an sich interessante untere Abschätzung des Graphen aller Punkte eines zu G gehörigen extremen Graphen benutzt. Mit Hilfe dieses Satzes wird eine, vom Verf. früher ohne Beweis mitgeteilte, obere Abschätzung von f(n; Kr(t,...,t)) als ein Spezialfall eines in vorliegender Arbeit bewiesenen allgemeineren Satzes (Satz 1) bewiesen, der für ein 2-chromatisches G eine obere Abschätzung von f(n; {G: Kr-2(t,...,t))} angibt; wobei allgemein ein Graph [G: Ks(p1,...,ps)] aus G durch Hinzunahme von Ks(p1,...,ps) nebst Verbindung aller neuen Punkte mit sämtlichen Punkten von G entsteht. Es werden auch einige Vermutungen mitgeteilt, außerdem eine – vom Verf. durch komplizierte Methoden bewiesene – Verschärfung von Satz 1 (ohne Beweis).
Reviewer: B.Andrásfai
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag