An improved error term for minimum H-decompositions of graphs

Autor(es)

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

Afiliação do(s) autor(es)

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

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

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 108, p. 92-101, SEP 2014.
• Citações Web of Science: 7

Resumo

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)

• Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
• Beneficiário: Julia Boettcher
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
• Beneficiário: Peter David Allen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado