Publications of (and about) Paul Erdös
Autor: Chung, F.R.K.; Erdös, Paul
Title: On unavoidable graphs. (In English)
Source: Combinatorica 3, 167-176 (1983).
Review: A graph G is called an (n,e)-unavoidable graph if every graph on n vertices and e edges contains G as a subgraph. Let f(n,e) denote the largest integer m with the property that there exists an (n,e)-unavoidable graph on m edges. In this paper the authors obtain bounds on f(n,e) which are in many cases asymptotically best possible.
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: subgraphs; Turan-like property; unavoidable graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag