Teresa Maria Jerónimo Sousa

The concept of H-decompositions of graphs was first introduced by Erdös, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decompositions of graphs.

"Given two r-graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part either is a single edge or forms a graph isomorphic to H. The minimum number of parts in an H-decomposition of G is denoted by φrH(G). By a 2-edge-decomposition of an r-graph we mean an H-decomposition for any fixed r-graph H with exactly 2 edges. In the special cases where the two edges of H intersect in exactly 1, 2 or r−1 vertices, these 2-edge-decompositions will be called bowtie, domino and kite, respectively. The value of the function φrH(n) will be obtained for bowtie, domino and kite decompositions of r-graphs.''