Аннотация
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$.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)