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

VL - 3

SP - 1719

EP - 1722

JO - Applied Mathematics

JF - Applied Mathematics

SN - 2152-7385

IS - 11

ER -