Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T05:19:32.239Z Has data issue: false hasContentIssue false
  • English
  • Français

A Density Corrádi–Hajnal Theorem

Published online by Cambridge University Press:  20 November 2018

Peter Allen ,
Julia Böttcher ,
Jan Hladký  and
Diana Piguet
Peter Allen
Affiliation:
Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK e-mail: [email protected], [email protected]
Julia Böttcher
Affiliation:
Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK e-mail: [email protected], [email protected]
Jan Hladký
Affiliation:
Institute of Mathematics of the Czech Academy of Sciences of the Czech Republic, Žitná 25, Praha, Czech Republic, The Institute of Mathematics is supported by RVO:67985840 e-mail: [email protected]
Diana Piguet
Affiliation:
New Technologies for Information Society, University of West Bohemia, Pilsen, Czech Republic e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 Corrádi–Hajnal Theorem.

Keywords

05C35graph theoryTuran's TheoremMantel's TheoremCorrádi–Hajnal Theoremtriangle
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 67 , Issue 4 , 01 August 2015 , pp. 721 - 758
Copyright
Copyright © Canadian Mathematical Society 2015

References

[ABHP] Allen, P., Böttcher, J., Hladký, J., and Piguet, D., An extension of Turán's Theorem, uniqueness, and stability. Electronic J. Combin. 21(2014), no. 4, P4.5.Google Scholar
[ABHP13] Allen, P., Böttcher, J., Hladký, J., and Piguet, D., Turánnical hypergraphs. Random Structures Algorithms 42(2013), no. 1, 29–58.http://dx.doi.org/10.1002/rsa.20399 Google Scholar
[CH63] Corrádi, K. and Hajnal, A., On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14(1963), 423–439.http://dx.doi.org/10.1007/BF01895727 Google Scholar
[EG59] Erdőos, P. and Gallai, T., On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar 10(1959, 337–356 (unbound insert).http://dx.doi.org/10.1007/BF02024498 Google Scholar
[Erd62a] Erdőos, P., On a theorem of Rademacher-Turán. Illinois J. Math. 6(1962), 122–127.Google Scholar
[Erd62b] Erdőos, P., Über ein Extremalproblem in der Graphentheorie. Arch. Math. 13(1962), 222–227.Google Scholar
[Erd65] Erdőos, P., A problem on independent r-tuples. Ann. Univ. Sci. Budapest. Eövötos Sect. Math. 8(1965), 93–95.Google Scholar
[Erd68] Erdőos, P., On some new inequalities concerning extremal properties of graphs. In: Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 77–81.Google Scholar
[GH12] Grosu, C. and Hladký, J.. The extremal function for partial bipartite tilings. European J. Combin., 33(5):807–815, 2012. http://dx.doi.org/10.1016/j.ejc.2011.09.026 Google Scholar
[Győo91] Győori, E.. On the number of edge disjoint cliques in graphs of given size. Combinatorica 11(1991), no. 3, 231–243. http://dx.doi.org/10.1007/BF01205075 Google Scholar
[HS70] Hajnal, A. and Szemerdi, E., Proof of a conjecture of P. Erdőos. In: Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, pp. 601–623.Google Scholar
[Kom00] Komlós, J., Tiling Turán theorems. Combinatorica 20(2000), no. 2, 203–218.http://dx.doi.org/10.1007/s004930070020 Google Scholar
[LS83] Lovász, L. and Simonovits, M., On the number of complete subgraphs of a graph. II. In: Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 459–495.Google Scholar
[Moo68] Moon, J. W., On independent complete subgraphs in a graph. Canad. J. Math. 20(1968), 95–102. http://dx.doi.org/10.4153/CJM-1968-012-x Google Scholar
[Raz08] Razborov, A. A., On the minimal density of triangles in graphs. Combin. Probab. Comput. 17(2008), no. 4, 603–618.Google Scholar
[Sim68] Simonovits, M., A method for solving extremal problems in graph theory, stability problems. In: Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319.Google Scholar