The H-Decomposition Problem for Graphs

Research output: Contribution to journalArticlepeer-review

Abstract

The concept of H-decompositions of graphs was first introduced by Erdos, 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 $\phi(n,H)$ be the smallest number $\phi$, such that, any graph of order n admits an H-decomposition with at most $\phi$ parts. The exact computation of $\phi(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.
Original language Unknown 1719-1722 Applied Mathematics 3 11 https://doi.org/10.4236/am.2012.311237 Published - 1 Jan 2012