%0 Generic %1 balogh2021trianglefree %A Balogh, József %A Clemen, Felix Christian %A Lidický, Bernard %D 2021 %K combinatorics maxcut %T Max Cuts in Triangle-free Graphs %U http://arxiv.org/abs/2103.14179 %X A well-known conjecture by Erd\Hos states that every triangle-free graph on $n$ vertices can be made bipartite by removing at most $n^2/25$ edges. This conjecture was known for graphs with edge density at least $0.4$ and edge density at most $0.172$. Here, we will extend the edge density for which this conjecture is true; we prove the conjecture for graphs with edge density at most $0.2486$ and for graphs with edge density at least $0.3197$. Further, we prove that every triangle-free graph can be made bipartite by removing at most $n^2/23.5$ edges improving the previously best bound of $n^2/18$.

@misc{balogh2021trianglefree, abstract = {A well-known conjecture by Erd\H{o}s states that every triangle-free graph on $n$ vertices can be made bipartite by removing at most $n^2/25$ edges. This conjecture was known for graphs with edge density at least $0.4$ and edge density at most $0.172$. Here, we will extend the edge density for which this conjecture is true; we prove the conjecture for graphs with edge density at most $0.2486$ and for graphs with edge density at least $0.3197$. Further, we prove that every triangle-free graph can be made bipartite by removing at most $n^2/23.5$ edges improving the previously best bound of $n^2/18$.}, added-at = {2022-02-14T08:25:20.000+0100}, author = {Balogh, József and Clemen, Felix Christian and Lidický, Bernard}, biburl = {https://www.bibsonomy.org/bibtex/2fe4e090c4e9f55971a6c8398f9fedec9/iliyasnoman}, description = {Max Cuts in Triangle-free Graphs}, interhash = {e4943971b9f9f50cdc4b53adcafcbf99}, intrahash = {fe4e090c4e9f55971a6c8398f9fedec9}, keywords = {combinatorics maxcut}, note = {cite arxiv:2103.14179Comment: This is an extended abstract submitted to EUROCOMB 2021. Comments are welcome}, timestamp = {2022-02-14T08:25:20.000+0100}, title = {Max Cuts in Triangle-free Graphs}, url = {http://arxiv.org/abs/2103.14179}, year = 2021 }