| Autor: |
József Balogh, Felix Christian Clemen, Bernard Lidický |
| Rok vydání: |
2021 |
| Předmět: |
|
| Zdroj: |
Trends in Mathematics ISBN: 9783030838225 |
| DOI: |
10.1007/978-3-030-83823-2_82 |
| Popis: |
A well-known conjecture by Erdő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\). |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
