Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 193.24302
Autor: Erdös, Pál
Title: On even subgraphs of graphs (In Hungarian)
Source: Mat. Lapok 18, 283-288 (1967).
Review: Bedeute G(n; m) einen Graphen mit n Knotenpunkten und m Kanten. Der Verf. hat früher bewiesen, daß jedes G(n; m) einen solchen paaren Graphen (d.h. 2-chromatischen Graphen) als Teilgraphen enthält, welcher mindestens 1/2 m Kanten besitzt; er hat ferner vermutet, daß es zu jedem dreieckfreien G(n; m) eine derartige Konstante c > 1/2 gibt, daß G(n; m) als Teilgraphen auch einen cm-kantigen paaren Graphen enthält. In vorliegender, auch diese Vermutung widerlegenden Arbeit beweist der Verf. den folgenden Satz:
Zu jedem \epsilon > 0 und k gibt es ein solches G(n; m), welches für gar kein l \leq k einen l-kantigen Kreis enthält, und als Teilgraphen auch keinen 1/2 m(1+\epsilon)-kantigen paaren Graphen enthält. Die Existenz eines dem Satz genügenden G(n; m) ergibt sich nicht durch unmittelbare Konstruktion; zum Beweis werden wahrscheinlichkeitstheoretische Methoden angewandt.
Reviewer: B.Andrásfai
Classif.: * 05C99 Graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag