Triangle-free subgraphs of random graphs
Allen, P.
, Böttcher, J., Roberts, B. & Kohayakawa, Y.
(2015-08-31 - 2015-09-04)
Triangle-free subgraphs of random graphs
[Paper]. European Conference on Combinatorics, Graph Theory and Applications, Bergen, Norway, NOR.
, Böttcher, J., Roberts, B. & Kohayakawa, Y.
(2015-08-31 - 2015-09-04)
Triangle-free subgraphs of random graphs
[Paper]. European Conference on Combinatorics, Graph Theory and Applications, Bergen, Norway, NOR.
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.