Minimum \(H\)-decompositions of graphs: edge-critical case (Q414645)

Given a graph \(H\) let \(\phi_{H}(n)\) denote the maximum number of parts that are needed to partition the edge set of any graph on \(n\) vertices such that every member of the partition is either a single edge or isomorphic to \(H\). Furthermore, let \(ex(n,H)\) denote the maximum size of a graph on \(n\) vertices not containing \(H\) as a subgraph. \textit{O. Pikhurko} and \textit{T. Sousa} [``Minimum \(H\)-decompositions of graphs,'' J. Comb. Theory, Ser. B 97, No.\,6, 1041--1055 (2007; Zbl 1125.05085)] conjectured that \(\phi_{H}(n)=ex(n,H)\) for \(\chi(H) \geq 3\) and all sufficiently large \(n\). Sousa verified the conjecture for clique extensions of order \(r \geq 4\) (\(n \geq r\)) [\textit{T. Sousa}, ``Decompositions of graphs into a given clique-extension,'' Ars Comb. 100, 465--472 (2011; Zbl 1265.05313)], the cycles of length 5 (\(n \geq 6\)) [\textit{T. Sousa}, ``Decompositions of graphs into 5-cycles and other small graphs,'' Electron. J. Comb. 12, No. 1, Research paper 49 (2005; Zbl 1079.05044)] and 7 (\(n \geq 10\)) [\textit{T. Sousa}, ``Decomposition of graphs into cycles of length seven and single edges,'' Ars Comb. (to appear)]. In this paper, the authors verify the conjecture for all edge-critical graphs. They also show that the graphs maximizing \(\phi_{H}(n)\) are \((\chi(H)-1)\)-partite Turán graphs.