An improved error term for minimum H-decompositions of graphs
Allen, P.
, Böttcher, J. & Person, Y.
(2014).
An improved error term for minimum H-decompositions of graphs.
Journal of Combinatorial Theory, Series B,
108, 92-101.
https://doi.org/10.1016/j.jctb.2014.03.001
, Böttcher, J. & Person, Y.
(2014).
An improved error term for minimum H-decompositions of graphs.
Journal of Combinatorial Theory, Series B,
108, 92-101.
https://doi.org/10.1016/j.jctb.2014.03.001
We consider partitions of the edge set of a graph G into copies of a fixed graph H and single edges. Let ϕH(n) denote the minimum number p such that any n-vertex G admits such a partition with at most p parts. We show that ϕH(n)=ex(n,Kr)+Θ(biex(n,H)) for χ(H)=r≥3, where biex(n,H) is the extremal number of the decomposition family of H. Since biex(n,H)=O(n2−γ) for some γ>0 this improves on the bound ϕH(n)=ex(n,H)+o(n2) by Pikhurko and Sousa (2007). In addition, it extends a result of Özkahya and Person (2012).