Many disjoint triangles in co-triangle-free graphs
| Autor: | Mykhaylo Tyomkyn |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Statistics and Probability
Disjoint union Conjecture Applied Mathematics Disjoint sets Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY FOS: Mathematics Bipartite graph Order (group theory) Mathematics - Combinatorics Combinatorics (math.CO) Stability theorem MathematicsofComputing_DISCRETEMATHEMATICS Complement (set theory) Mathematics |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|