J. Balogh, F. Clemen, и B. Lidický. (2021)cite arxiv:2103.14179Comment: This is an extended abstract submitted to EUROCOMB 2021. Comments are welcome.
Аннотация
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$.
%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
}