On directed triangles in digraphs

Peter Hamburger, Penny Haxell, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review

Abstract

Using a recent result of Chudnovsky, Seymour, and Sullivan, we slightly improve two bounds related to the Caccetta-Haggkvist Conjecture. Namely, we show that if α ≥ 0.35312, then each n-vertex digraph D with minimum outdegree at least an has a directed β-cycle. If β ≥ 0.34564, then every n-vertex digraph D in which the outdegree and the indegree of each vertex is at least βn has a directed 3-cycle.

Original languageEnglish (US)
Article numberN19
JournalElectronic Journal of Combinatorics
Volume14
Issue number1 N
DOIs
StatePublished - Sep 7 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On directed triangles in digraphs'. Together they form a unique fingerprint.

Cite this