Campus Units
Mathematics
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
3-25-2021
Journal or Book Title
arXiv
Abstract
A well-known conjecture by Erdős states that every triangle-free graph on n vertices can be made bipartite by removing at most n2/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 n2/23.5 edges improving the previously best bound of n2/18.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright Owner
The Authors
Copyright Date
2021
Language
en
File Format
application/pdf
Recommended Citation
Balogh, József; Clemen, Felix Christian; and Lidicky, Bernard, "Max Cuts in Triangle-free Graphs" (2021). Mathematics Publications. 267.
https://lib.dr.iastate.edu/math_pubs/267
Comments
This preprint is made available through arXiv: https://arxiv.org/abs/2103.14179.