An improved error term for minimum H-decompositions of graphs

Author(s)

Allen, Peter ^[1] ; Boettcher, Julia ^[1] ; Person, Yury ^[2]

Affiliation

^[1] London Sch Econ, Dept Math, London WC2A 2AE - England

^[2] Goethe Univ Frankfurt, Inst Math, D-60325 Frankfurt - Germany

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 108, p. 92-101, SEP 2014.
• Web of Science Citations: 7

Abstract

We consider partitions of the edge set of a graph G into copies of a fixed graph H and single edges. Let phi(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 phi(H)(n) = ex(n, K-r) + Theta(biex(n, H)) for x (H) = r >= 3, where biex(n, H) is the extremal number of the decomposition family of H. Since biex(n, H) = O(n(2-gamma)) for some gamma > 0 this improves on the bound phi(H)(n)= ex(n, o(n(2)) by Pikhurko and Sousa (2007) {[}6]. In addition, it extends a result of Ozkahya and Person (2012) {[}5]. (C) 2014 Elsevier Inc. All rights reserved. (AU)

• FAPESP's process: 09/17831-7 - Embedding and packing problems in extremal graph theory
• Grantee: Julia Boettcher
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory
• Grantee: Peter David Allen
• Support Opportunities: Scholarships in Brazil - Post-Doctoral