Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 187.21003
Autor: Erdös, Pál
Title: Some recent results on extremal problems in graph theory. (Results) (In English)
Source: Theory Graphs, Int. Symp. Rome 1966, 117-123 (English), 124-130 (French) (1967).
Review: [For the entire collection see Zbl 155.00201.]
Bezeichne l = f(n; Gi,...,Gk) die kleinste Zahl, für welche jeder n-punktige und l-kantige Graph mindestens einen der Graphen Gi (i = 1,2,...,k) als einen Teilgraphen enthält. In vorliegender Arbeit werden ohne Beweise verschiedene Behauptungen und Vermutungen bezüglich derartiger Zahlen mitgeteilt; darunter auch das folgende gemeinsame Ergebnis von M.Simonovits und dem Verf. [Studia Sci. Math. Hung. 1, 51-57 (1966; Zbl 178.27301)]: limn ––> oo f(n; G1,...,Gk)/n2 = 1/2 (1-{1\over r-1}), wobei r die minimale chromatische Zahl der Gi bezeichnet. Hier wird für folgende Verschärfung dieses Satzes ein Beweis (durch Vermittlung eines stärkeren Satzes) im Fall r = 3 ausführlich, im Fall r > 3 in kurzen Umrissen dargelegt: Bezeichne Ks(p1,...,ps) den vollständigen s-chromatischen Graphen, welcher pi Punkte der i-ten Farbe besitzt, und dessen je zwei verschiedengefärbte Punkte verbunden sind. Sei G ein n-punktiger extremer Graph der Kantenzahl f(n; G1,...,Gk)-1, welcher keinen der Graphen Gi enthält. Dann gibt es einen Graphen Kr-1(p1,...,pr-1) mit sumi = 1r-1 pi = n und pi = (1+o(1)) {n \over r-1} für i = 1,...,r-1, aus dem sich G durch Hinzunahme und Entfernung von Kanten der Anzahl o(n2) ergibt.
Reviewer: A.Andrásfai
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag