The *H*-Decomposition Problem for Graphs

Author(s)
Teresa Sousa

ABSTRACT

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.

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.

Cite this paper

T. Sousa, "The*H*-Decomposition Problem for Graphs," *Applied Mathematics*, Vol. 3 No. 11, 2012, pp. 1719-1722. doi: 10.4236/am.2012.311237.

T. Sousa, "The

References

[1] B. Bollobás, “Modern Graph Theory,” Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0619-4

[2] P. Turán, “On an Extremal Problem in Graph Theory,” Matematikai és Fisikai Lapok, Vol. 48, 1941, pp. 436-452.

[3] D. Dor and M. Tarsi, “Graph Decomposition Is NPComplete: A Complete Proof of Holyer’s Conjecture,” SIAM Journal on Computing, Vol. 26, No. 4, 1997, pp. 1166-1187. doi:10.1137/S0097539792229507

[4] P. Erd?s, A. W. Goodman and L. Pósa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, 1966, pp. 106-112. doi:10.4153/CJM-1966-014-3

[5] B. Bollobás, “On Complete Subgraphs of Different Orders,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 79, No. 1, 1976, pp. 19-24. doi:10.1017/S0305004100052063

[6] O. Pikhurko and T. Sousa, “Minimum H-Decompositions of Graphs,” Journal of Combinatorial Theory, Series B, Vol. 97, No. 6, 2007, pp. 1041-1055. doi:10.1016/j.jctb.2007.03.002

[7] T. Sousa, “Decompositions of Graphs into 5-Cycles and Other Small Graphs,” Electronic Journal of Combinatorics, Vol. 12, No. R49, 2005, 7 pp.

[8] T. Sousa, “Decompositions of Graphs into Cycles of Length Seven and Single Edges,” ARS Combinatoria, in Press.

[9] T. Sousa, “Decompositions of Graphs into a Given Clique-Extension,” ARS Combinatoria, Vol. 100, 2011, pp. 465-472.

[10] L. ?zkahya and Y. Person, “Minimum H-Decompositions of Graphs: Edge-Critical Case,” Journal of Combinatorial Theory, Series B, Vol. 102, No. 3, 2012, pp. 715-725. doi:10.1016/j.jctb.2011.10.004

[11] T. Sousa. “Minimum Weight H-Decompositions of Graphs: The Bipartite Case,” Electronic Journal of Combinatorics, Vol. 18, No. 1, 2011, pp. 126-135.

[12] H. Liu and T. Sousa, “Monochromatic Kr-Decompositions of Graphs,” Unpublished.

[13] R. E. Greenwood and A. M. Gleason, “Combinatorial Relations and Chromatic Graphs,” Canadian Journal of Mathematics, Vol. 7, 1955, pp. 1-7. doi:10.4153/CJM-1955-001-4

[1] B. Bollobás, “Modern Graph Theory,” Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0619-4

[2] P. Turán, “On an Extremal Problem in Graph Theory,” Matematikai és Fisikai Lapok, Vol. 48, 1941, pp. 436-452.

[3] D. Dor and M. Tarsi, “Graph Decomposition Is NPComplete: A Complete Proof of Holyer’s Conjecture,” SIAM Journal on Computing, Vol. 26, No. 4, 1997, pp. 1166-1187. doi:10.1137/S0097539792229507

[4] P. Erd?s, A. W. Goodman and L. Pósa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, 1966, pp. 106-112. doi:10.4153/CJM-1966-014-3

[5] B. Bollobás, “On Complete Subgraphs of Different Orders,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 79, No. 1, 1976, pp. 19-24. doi:10.1017/S0305004100052063

[6] O. Pikhurko and T. Sousa, “Minimum H-Decompositions of Graphs,” Journal of Combinatorial Theory, Series B, Vol. 97, No. 6, 2007, pp. 1041-1055. doi:10.1016/j.jctb.2007.03.002

[7] T. Sousa, “Decompositions of Graphs into 5-Cycles and Other Small Graphs,” Electronic Journal of Combinatorics, Vol. 12, No. R49, 2005, 7 pp.

[8] T. Sousa, “Decompositions of Graphs into Cycles of Length Seven and Single Edges,” ARS Combinatoria, in Press.

[9] T. Sousa, “Decompositions of Graphs into a Given Clique-Extension,” ARS Combinatoria, Vol. 100, 2011, pp. 465-472.

[10] L. ?zkahya and Y. Person, “Minimum H-Decompositions of Graphs: Edge-Critical Case,” Journal of Combinatorial Theory, Series B, Vol. 102, No. 3, 2012, pp. 715-725. doi:10.1016/j.jctb.2011.10.004

[11] T. Sousa. “Minimum Weight H-Decompositions of Graphs: The Bipartite Case,” Electronic Journal of Combinatorics, Vol. 18, No. 1, 2011, pp. 126-135.

[12] H. Liu and T. Sousa, “Monochromatic Kr-Decompositions of Graphs,” Unpublished.

[13] R. E. Greenwood and A. M. Gleason, “Combinatorial Relations and Chromatic Graphs,” Canadian Journal of Mathematics, Vol. 7, 1955, pp. 1-7. doi:10.4153/CJM-1955-001-4