A Density Corradi-Hajnal Theorem

Autor(es)

Allen, Peter ^[1] ; Boettcher, Julia ^[1] ; Hladky, Jan ^[2] ; Piguet, Diana ^[3]

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

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

^[2] Czech Acad Sci Czech Republ, Inst Math, Prague - Czech Republic

^[3] Univ W Bohemia, New Technol Informat Soc, Plzen - Czech Republic

• Tipo de documento: Artigo Científico
• Fonte: CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES; v. 67, n. 4, p. 721-758, AUG 2015.
• Citações Web of Science: 4

Resumo

We find, for all sufficiently large n and each k, the maximum number of edges in an n-vertex graph that does not contain k + 1 vertex-disjoint triangles. This extends a result of Moon {[}Canad. J. Math. 20 (1968), 96-102], which is in turn an extension of Mantel's Theorem. Our result can also be viewed as a density version of the Corradi-Hajnal Theorem. (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