%0 Journal Article
%T The <i>H</i>-Decomposition Problem for Graphs
%A Teresa Sousa
%J Applied Mathematics
%P 1719-1722
%@ 2152-7393
%D 2012
%I Scientific Research Publishing
%R 10.4236/am.2012.311237
%X 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-Decom- positions of graphs.
%K Graph Decompositions
%K Weighted Graph Decompositions
%K Monochromatic Graph Decompositions
%K Tur&#225
%K n Graph
%K Ramsey Numbers
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=24522