Minimum \(H\)-decompositions of graphs (Q2384810): Difference between revisions

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 \(\varphi_H(n)\) be the smallest number \(\varphi\) such that any graph \(G\) of order \(n\) admits an \(H\)-decomposition with at most \(\varphi\) parts. One of the main results says: Let \(H\) be any fixed graph of chromatic number \(r\geq 3\). Then, \(\varphi_H(n)=t_{r-1}(n)+ o(n^2)\), where \(t_{r-1}(n)\) is the maximum size of an \((r-1)\)-partite graph of order \(n\). In addition, in the case that \(H\) is bipartite, the authors determine \(\varphi_H(n)\) with a constant additive error and provide an algorithm returning the exact value with running time polynomial in \(\log n\).