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
