Minimum H-Decompositions of Graphs
- Citation:
- Pikhurko, Oleg, and Teresa Sousa. "Minimum H-Decompositions of Graphs." Journal of Combinatorial Theory, B. 97 (2007): 1041-1055.
Abstract:
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 φH(n) be the smallest number φ such that every graph G of order n admits an H-decomposition with at most φ parts. In the paper it is proved that φH(n)=tr−1(n)+o(n2) for every graph H of chromatic number r≥3, where tr(n) is the maximum size of an r-partite graph of order n. Moreover, when H is bipartite, the authors determine φH(n) with a constant additive error.
