CaltechAUTHORS
  A Caltech Library Service

Many disjoint triangles in co-triangle-free graphs

Tyomkyn, Mykhaylo (2021) Many disjoint triangles in co-triangle-free graphs. Combinatorics, Probability and Computing, 30 (1). pp. 153-162. ISSN 0963-5483. https://resolver.caltech.edu/CaltechAUTHORS:20210318-085323811

[img] PDF - Accepted Version
See Usage Policy.

150Kb
[img] Plain Text - Supplemental Material
See Usage Policy.

14Kb
[img] Plain Text - Supplemental Material
See Usage Policy.

9Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210318-085323811

Abstract

We prove that any n-vertex graph whose complement is triangle-free contains n²/12 – o(n²) 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1017/s096354832000036xDOIArticle
https://arxiv.org/abs/2001.00763arXivDiscussion Paper
Additional Information:© The Author(s), 2020. Published by Cambridge University Press. Received 28 January 2020; revised 15 June 2020; first published online 14 August 2020. I would like to thank David Conlon for helpful discussions and Olga Goulko for help with setting up the computer simulation.
Issue or Number:1
Classification Code:2020 MSC Codes: 05C35, 05C70
Record Number:CaltechAUTHORS:20210318-085323811
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210318-085323811
Official Citation:Tyomkyn, M. (2021). Many disjoint triangles in co-triangle-free graphs. Combinatorics, Probability and Computing, 30(1), 153-162. doi:10.1017/S096354832000036X
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108473
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:19 Mar 2021 00:22
Last Modified:19 Mar 2021 00:22

Repository Staff Only: item control page