Geodesic
A Density Corrádi–Hajnal Theorem
Canadian journal of mathematics, Tome 67 (2015) no. 4, pp. 721-758

Voir la notice de l'article provenant de la source Cambridge University Press

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.
DOI : 10.4153/CJM-2014-030-6
Mots-clés : 05C35, graph theory, Turan's Theorem, Mantel's Theorem, Corrádi–Hajnal Theorem, triangle 
Allen, Peter; Böttcher, Julia; Hladký, Jan; Piguet, Diana. A Density Corrádi–Hajnal Theorem. Canadian journal of mathematics, Tome 67 (2015) no. 4, pp. 721-758. doi: 10.4153/CJM-2014-030-6
@article{10_4153_CJM_2014_030_6,
     author = {Allen, Peter and B\"ottcher, Julia and Hladk\'y, Jan and Piguet, Diana},
     title = {A {Density} {Corr\'adi{\textendash}Hajnal} {Theorem}},
     journal = {Canadian journal of mathematics},
     pages = {721--758},
     year = {2015},
     volume = {67},
     number = {4},
     doi = {10.4153/CJM-2014-030-6},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-030-6/}
}
TY  - JOUR
AU  - Allen, Peter
AU  - Böttcher, Julia
AU  - Hladký, Jan
AU  - Piguet, Diana
TI  - A Density Corrádi–Hajnal Theorem
JO  - Canadian journal of mathematics
PY  - 2015
SP  - 721
EP  - 758
VL  - 67
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-030-6/
DO  - 10.4153/CJM-2014-030-6
ID  - 10_4153_CJM_2014_030_6
ER  - 
%0 Journal Article
%A Allen, Peter
%A Böttcher, Julia
%A Hladký, Jan
%A Piguet, Diana
%T A Density Corrádi–Hajnal Theorem
%J Canadian journal of mathematics
%D 2015
%P 721-758
%V 67
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-030-6/
%R 10.4153/CJM-2014-030-6
%F 10_4153_CJM_2014_030_6

[ABHP] [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] [ABHP13] Allen, P., Böttcher, J., Hladký, J., and Piguet, D., Turánnical hypergraphs. Random Structures Algorithms 42(2013), no. 1, 29–58. Google Scholar | DOI

[CH63] [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. Google Scholar | DOI

[EG59] [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). Google Scholar | DOI

[Erd62a] [Erd62a] Erdőos, P., On a theorem of Rademacher-Turán. Illinois J. Math. 6(1962), 122–127. Google Scholar

[Erd62b] [Erd62b] Erdőos, P., Über ein Extremalproblem in der Graphentheorie. Arch. Math. 13(1962), 222–227. Google Scholar

[Erd65] [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] [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] [GH12] Grosu, C. and Hladký, J.. The extremal function for partial bipartite tilings. European J. Combin., 33(5):807–815, 2012. Google Scholar | DOI

[Győo91] [Győo91] Győori, E.. On the number of edge disjoint cliques in graphs of given size. Combinatorica 11(1991), no. 3, 231–243. Google Scholar | DOI

[HS70] [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] [Kom00] Komlós, J., Tiling Turán theorems. Combinatorica 20(2000), no. 2, 203–218. Google Scholar | DOI

[LS83] [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] [Moo68] Moon, J. W., On independent complete subgraphs in a graph. Canad. J. Math. 20(1968), 95–102. Google Scholar | DOI

[Raz08] [Raz08] Razborov, A. A., On the minimal density of triangles in graphs. Combin. Probab. Comput. 17(2008), no. 4, 603–618. Google Scholar

[Sim68] [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

Cité par Sources :