CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Author's Draft

A density Corrádi-Hajnal Theorem

  • Peter Allen,
    Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK
  • Julia Böttcher,
    Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK
  • Jan Hladký,
    DIMAP and Mathematics Institute, University of Warwick, Coventry, CV4~7AL, UK
  • Diana Piguet,
    New Technologies for Information Society, University of West Bohemia, Pilsen, Czech Republic
Format:   LaTeX   MathJax   PDF  

Abstract

We find, for all sufficiently large $n$ and each $k$, the maximum number of edges in an $n$-vertex graph which 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 Corrádi-Hajnal Theorem.
Keywords: graph theory, Turan's Theorem, Mantel's Theorem, Corrádi-Hajnal Theorem, triangle graph theory, Turan's Theorem, Mantel's Theorem, Corrádi-Hajnal Theorem, triangle
MSC Classifications: 05C35 show english descriptions Extremal problems [See also 90C35] 05C35 - Extremal problems [See also 90C35]
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/