OFFSET
1,4
COMMENTS
A maximal triangle-free graph is a triangle-free graph so that the insertion of each new edge introduces a triangle. For graphs of order larger than 2 this is equivalent to being triangle-free and having diameter 2.
Almost all triangle-free graphs are bipartite (as follows from Erdős-Kleitman-Rothschild). However, most of the bipartite graphs are not maximal, which prompted Erdős to pose a problem about enumeration of maximal triangle-free graphs. The problem was solved by Balogh and Petříčková in 2014 using the recently developed hypergraph container method. In 2015 Balogh, Liu, Petříčková and Sharifzadeh showed that almost every maximal triangle-free graph G admits a vertex partition X union Y such that G[X] is a perfect matching and Y is an independent set. - Elijah Beregovsky, Oct 09 2025
REFERENCES
S. Brandt, G. Brinkmann and T. Harmuth, The Generation of Maximal Triangle-Free Graphs, Graphs and Combinatorics, 16 (2000), 149-157.
LINKS
József Balogh and Šárka Petříčková, The number of the maximal triangle-free graphs, arXiv:1409.8123 [math.CO], 2014.
József Balogh, Hong Liu, Šárka Petříčková and Maryam Sharifzadeh, The typical structure of maximal triangle-free graphs, arXiv:1501.02849 [math.CO], 2015.
S. Brandt, G. Brinkmann and T. Harmuth, MTF.
Gunnar Brinkmann, Jan Goedgebeur and J.C. Schlage-Puchta, triangleramsey.
Gunnar Brinkmann, Jan Goedgebeur, and Jan-Christoph Schlage-Puchta, Ramsey numbers R(K3,G) for graphs of order 10, arXiv 1208.0501 (2012).
P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of k_n-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.
Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs, arXiv:1707.07581 [math.CO] (2017).
House of Graphs, Maximal triangle-free graphs.
Hong Liu, Lecture 16. The number of maximal triangle-free graphs, 2021.
M. Simonovits, Paul Erdös' influence on extremal graph theory, The Mathematics of Paul Erdös, II (R. L. Graham and J. Nešetril, eds.), 148-192, Springer-Verlag, Berlin, 1996.
FORMULA
a(n) = 2^(n^2/8 + o(n^2)) (Balogh and Petříčková). - Elijah Beregovsky, Oct 09 2025
CROSSREFS
KEYWORD
nonn
AUTHOR
Jan Goedgebeur, Sep 18 2012
EXTENSIONS
a(24) added by Jan Goedgebeur, Jun 05 2018
STATUS
approved