Maximum directed cuts in acyclic digraphs

Noga Alon, Béla Bollobás, András Gyárfás, Jenö Lehel, Alex Scott

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs.

Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalJournal of Graph Theory
Volume55
Issue number1
DOIs
StatePublished - May 2007

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Directed and acyclic graphs
  • Directed cut
  • Extremal problems
  • Maximum cut

Fingerprint Dive into the research topics of 'Maximum directed cuts in acyclic digraphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Bollobás, B., Gyárfás, A., Lehel, J., & Scott, A. (2007). Maximum directed cuts in acyclic digraphs. Journal of Graph Theory, 55(1), 1-13. https://doi.org/10.1002/jgt.20215