## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  807.05040
Autor:  Erdös, Paul; Holzman, Ron
Title:  On maximal triangle-free graphs. (In English)
Source:  J. Graph Theory 18, No.6, 585-594 (1994).
Review:  The paper examines maximal triangle-free graphs (i.e. graphs that cease to be triangle-free upon adding any new edge) with few edges, satisfying a constraint in the form of an upper bound on the degrees.
Let F(n,D) be the minimum number of edges of a maximal triangle-free graph on n vertices having maximal degree at most D. By continuing work done by Z. Füredi and Á. Seress, it is proven that
 limn ––> oo {F(n,cn)\over n} = (11- 7c)/2 for 3/7 \leq c < 1/2 4 for 2/5 \leq c \leq 3/7
which contradicts a conjecture of them.
Reviewer:  E.Ederle (München)
Classif.:  * 05C35 Extremal problems (graph theory)
05C65 Hypergraphs
90C05 Linear programming
Keywords:  maximal triangle-free graphs; upper bound

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag