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 journalArticlepeer-review

25 Scopus citations


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
Issue number1
StatePublished - May 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


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


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

Cite this