The typical structure of maximal triangle-free graphs

József Balogh, Hong Liu, v Sárka Petv ri v cková, Maryam Sharifzadeh

Research output: Contribution to journalArticlepeer-review


Recently, settling a question of Erdos, Balogh, and Petřríčková showed that there are at most 2 n2/8+o(n2) n-vertex maximal triangle-free graphs, matching the previously known lower bound. Here, we characterize the typical structure of maximal triangle-free graphs. We show that almost every maximal triangle-free graph G admits a vertex partition X ∪ Y such that GTXU is a perfect matching and Y is an independent set. Our proof uses the Ruzsa-Szemerédi removal lemma, the Erdos-Simonovits stability theorem, and recent results of Balogh, Morris, and Samotij and Saxton and Thomason on characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint P 3s, which is of independent interest.

Original languageEnglish (US)
Article numbere20
Pages (from-to)e20, 19
JournalForum Math. Sigma
StatePublished - 2015

ASJC Scopus subject areas

  • Analysis
  • Theoretical Computer Science
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'The typical structure of maximal triangle-free graphs'. Together they form a unique fingerprint.

Cite this