On Directed Triangles in Digraphs

  • Peter Hamburger
  • Penny Haxell
  • Alexandr Kostochka

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 $\alpha\geq 0.35312$, then each $n$-vertex digraph $D$ with minimum outdegree at least $\alpha n$ has a directed $3$-cycle. If $\beta\geq 0.34564$, then every $n$-vertex digraph $D$ in which the outdegree and the indegree of each vertex is at least $\beta n$ has a directed $3$-cycle.

Published
2007-09-07
Article Number
N19