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.

Comments

This preprint is made available through arXiv: https://arxiv.org/abs/2103.14179.

Creative Commons License

Creative Commons Attribution 4.0 License
This work is licensed under a Creative Commons Attribution 4.0 License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS