##
**Zentralblatt MATH**

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

**Zbl.No: ** 491.05049

**Autor: ** Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.

**Title: ** Minimal decompositions of graphs into mutually isomorphic subgraphs. (In English)

**Source: ** Combinatorica 1, 13-24 (1981).

**Review: ** Let G = **{**G_{1},...,G_{k}**}** be a collection of n-vertex graphs each with the same (unspecified) number of edges. Let U(G) be the least r for which there exists a set of partitions of the edge sets E(G_{i}) of the graph into r parts, say E(G_{i}) = \cup_{j = 1}^{r} E_{ij}, such that for each j, all the E_{ij} are isomorphic as graphs, 1 \leq i \leq k. Let U_{k}(n) denote the largest value U(G) can take with G as above. The authors and other earlier showed [Congr. Numerantium 23, 3-18 (1979; Zbl 434.05046)] that U_{2}(n) = 2n/3+o() as n ––> oo. Here they show U_{k}(n) = 3n/4+o(n) for any fixed k \geq 3, as n ––> oo. The difficult part of the proof is the establishment of the upper bound. Broadly speaking, it is done by successively removing subgraphs which are shown to be common to all the G_{i}, where the subgraph removed at any state depends on the number of edges in the G_{i}.

**Reviewer: ** N.Wormald

**Classif.: ** * 05C70 Factorization, etc.

05C35 Extremal problems (graph theory)

**Keywords: ** factorization; partition of edge set

**Citations: ** Zbl.434.05046

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag