Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  105.17504
Autor:  Erdös, Pál
Title:  Über ein Extremalproblem in der Graphentheorie. (On an extremal problem in graph theory.) (In German)
Source:  Arch. Math. 13, Festschrift Reinhold Baer 222-227 (1962).
Review:  The author considers graphs without loops or multiple edges. He proves that, if n \geq 400 k2, every graph with n vertices and at least

l = [ 1/4 (n-k+1)2]+(k-1) (n- 1/2 k+1)

edges contains k disjoint triangles, with the exception of an (up to isomorphism) unique graph with n vertices and l edges. He states that a more complicated version of the proof can replace 400 k2 by Ck, where C is an absolute constant. The following further theorems are stated with brief hints for proof. Let G be a graph with n vertices. (1) If k \equiv n (mod 2) and every vertex has valency \geq 1/2 (n+k) and n \geq some n0(k), then G contains k disjoint triangles. (2) If n > ck, where c is a sufficiently large absolute constant, and G has 1/4 n2+k edges, then G contains k triangles no two of which have a common edge.
Reviewer:  C.St.J.A.Nash-Williams
Classif.:  * 05C35 Extremal problems (graph theory)
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page