Publications

Export 1 results:
Sort by: [ Author  (Desc)] Title Type Year
A B C D E F G H I J K L M N O [P] Q R S T U V W X Y Z   [Show ALL]
P
Pikhurko, Oleg, and Teresa Sousa. "Minimum H-Decompositions of Graphs." Journal of Combinatorial Theory, B. 97 (2007): 1041-1055. Abstracth_decomposition.pdfWebsite

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.