TY - JOUR
T1 - The H-Decomposition Problem for Graphs
AU - Sousa, Teresa Maria Jerónimo
PY - 2012/1/1
Y1 - 2012/1/1
N2 - 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.
AB - 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.
KW - Turán Graph
KW - Monochromatic Graph Decompositions
KW - Graph Decompositions
KW - Ramsey Numbers
KW - Weighted Graph Decompositions
U2 - 10.4236/am.2012.311237
DO - 10.4236/am.2012.311237
M3 - Article
SN - 2152-7385
VL - 3
SP - 1719
EP - 1722
JO - Applied Mathematics
JF - Applied Mathematics
IS - 11
ER -