Triangle-free subgraphs of random graphs
Allen, Peter
; Böttcher, Julia; Roberts, Barnaby; and Kohayakawa, Yoshiharu
(2015)
Triangle-free subgraphs of random graphs
In: European Conference on Combinatorics, Graph Theory and Applications, 2015-08-31 - 2015-09-04, Bergen,Norway,NOR.
(Submitted)
; Böttcher, Julia; Roberts, Barnaby; and Kohayakawa, Yoshiharu
(2015)
Triangle-free subgraphs of random graphs
In: European Conference on Combinatorics, Graph Theory and Applications, 2015-08-31 - 2015-09-04, Bergen,Norway,NOR.
(Submitted)
The Andrásfai-Erdős-Sós Theorem [2] states that all triangle-free graphs on n vertices with minimum degree strictly greater than 2n/5 are bipartite. Thomassen [11] proved that when the minimum degree condition is relaxed to ( 1 3 + ε)n, the result is still guaranteed to be rε-partite, where rε does not depend on n. We prove best possible random graph analogues of these theorems.
-
picture_as_pdf
Downloads