No CrossRef data available.
Article contents
Many disjoint triangles in co-triangle-free graphs
Part of:
Graph theory
Published online by Cambridge University Press: 14 August 2020
Abstract
We prove that any n-vertex graph whose complement is triangle-free contains n2/12 – o(n2) edge-disjoint triangles. This is tight for the disjoint union of two cliques of order n/2. We also prove a corresponding stability theorem, that all large graphs attaining the above bound are close to being bipartite. Our results answer a question of Alon and Linial, and make progress on a conjecture of Erdős.
MSC classification
Primary:
05C35: Extremal problems
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2020. Published by Cambridge University Press
References
Alon, N., Shapira, A. and Sudakov, B. (2009) Additive approximation for edge-deletion problems. Ann. of Math. 170 371–411.CrossRefGoogle Scholar
Erdös, P. (1997) Some recent problems and results in graph theory. Discrete Math. 164 81–85.CrossRefGoogle Scholar
Erdös, P., Faudree, R. J., Gould, R. J., Jacobson, M. S. and Lehel, J. (1997) Edge disjoint monochromatic triangles in 2-colored graphs. Discrete Math. 164 81–85.CrossRefGoogle Scholar
Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.CrossRefGoogle Scholar
Haxell, P. and Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica 21 13–38.CrossRefGoogle Scholar
Keevash, P. and Sudakov, B. (2004) Packing triangles in a graph and its complement. J. Graph Theory 47 203–216.CrossRefGoogle Scholar
Yuster, R. (2007) Packing cliques in graphs with independence number 2. Combin. Probab. Comput. 16 805–817.CrossRefGoogle Scholar
Tyomkyn supplementary material
Tyomkyn supplementary material 1
File
14.7 KB
Tyomkyn supplementary material
Tyomkyn supplementary material 2
File
9.9 KB