1,2,...,r. Then this pair of partitions is a U-decomposition of the pair of graphs. U(G,G') is defined to be the minimum value of r for which a U-decomposition exists. The paper considers many properties of U(G,G') and of U(n') defined as **max** U(G,G') where ''max'' ranges over all pairs (G,G') of graphs with n vertices. The main result of the paper is that U(n) = 2n/3+0(n).

**Reviewer: ** R.S.Read

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** isomorphism; edge-chromatic number; edge-dominating number; decomposition

**Citations: ** Zbl.418.00002

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag