##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 397.05019

**Autor: ** Erdös, Paul; Hechler, Stephen H.; Kainen, Paul

**Title: ** On finite superuniversal graphs. (In English)

**Source: ** Discrete Math. 24, 235-249 (1978).

**Review: ** The author's abstract: ''Define a simple graph G to be k-superuniversal if for any k-element simple graph K and for any full subgraph H of K every full embedding of H into G can be extended to a full embedding of K into G. We prove that for each positive integer k there exist finite k-superuniversalgraphs, and we find upper and lower bounds on the smallest such graphs. We also find various bounds on the number of edges as well as the maximal and minimal valence of a k-superuniversal graph. We then generalize the notion of k-superuniversality to cover graphs with colorings and prove similar and related theorems.'' Note: The g(u) in Definition 3.1. should be f(v).

**Reviewer: ** R.L.Hemminger

**Classif.: ** * 05C10 Topological graph theory

05C15 Chromatic theory of graphs and maps

**Keywords: ** finite superuniversal graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag