Max Cuts in Triangle-Free Graphs

József Balogh, Felix Christian Clemen, Bernard Lidický

Research output: Chapter in Book/Report/Conference proceedingChapter

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.

Original languageEnglish (US)
Title of host publicationTrends in Mathematics
PublisherSpringer
Pages509-514
Number of pages6
DOIs
StatePublished - 2021

Publication series

NameTrends in Mathematics
Volume14
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X

Keywords

  • Extremal combinatorics
  • Graph theory
  • Triangle-free graphs

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Max Cuts in Triangle-Free Graphs'. Together they form a unique fingerprint.

Cite this