Geodesic
THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS
Forum of Mathematics, Sigma, Tome 3 (2015)

Voir la notice de l'article provenant de la source Cambridge University Press

Recently, settling a question of Erdős, Balogh, and Petříčková showed that there are at most $2^{n^{2}/8+o(n^{2})}$$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\cup Y$ such that $G[X]$ is a perfect matching and $Y$ is an independent set.Our proof uses the Ruzsa–Szemerédi removal lemma, the Erdős–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_{3}$s, which is of independent interest. 
@article{10_1017_fms_2015_22,
     author = {J\'OZSEF BALOGH and HONG LIU and \v{S}\'ARKA PET\v{R}\'I\v{C}KOV\'A and MARYAM SHARIFZADEH},
     title = {THE {TYPICAL} {STRUCTURE} {OF} {MAXIMAL} {TRIANGLE-FREE} {GRAPHS}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {3},
     year = {2015},
     doi = {10.1017/fms.2015.22},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.22/}
}
TY  - JOUR
AU  - JÓZSEF BALOGH
AU  - HONG LIU
AU  - ŠÁRKA PETŘÍČKOVÁ
AU  - MARYAM SHARIFZADEH
TI  - THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS
JO  - Forum of Mathematics, Sigma
PY  - 2015
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.22/
DO  - 10.1017/fms.2015.22
LA  - en
ID  - 10_1017_fms_2015_22
ER  - 
%0 Journal Article
%A JÓZSEF BALOGH
%A HONG LIU
%A ŠÁRKA PETŘÍČKOVÁ
%A MARYAM SHARIFZADEH
%T THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS
%J Forum of Mathematics, Sigma
%D 2015
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.22/
%R 10.1017/fms.2015.22
%G en
%F 10_1017_fms_2015_22
JÓZSEF BALOGH; HONG LIU; ŠÁRKA PETŘÍČKOVÁ; MARYAM SHARIFZADEH. THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS. Forum of Mathematics, Sigma, Tome 3 (2015). doi: 10.1017/fms.2015.22

Cité par Sources :