Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-24T12:57:10.540Z Has data issue: false hasContentIssue false
  • English
  • Français

Many disjoint triangles in co-triangle-free graphs

Part of: Graph theory

Published online by Cambridge University Press:  14 August 2020

Mykhaylo Tyomkyn
Mykhaylo Tyomkyn*
Affiliation:
Department of Mathematics, California Institute of Technology, Pasadena, CA91125, USA
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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
Secondary: 05C70: Factorization, matching, partitioning, covering and packing
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 1 , January 2021 , pp. 153 - 162
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Supplementary material: File

Tyomkyn supplementary material

Tyomkyn supplementary material 1

Download Tyomkyn supplementary material(File)
File 14.7 KB
Supplementary material: File

Tyomkyn supplementary material

Tyomkyn supplementary material 2

Download Tyomkyn supplementary material(File)
File 9.9 KB