On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs

Details On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs

2009-09-14

arxiv.org/abs/0909.2468v1

Mathematics

Combinatorics

5 pages

Scientific paper

For a simple digraph $G$ without directed triangles or digons, let $\beta(G)$ be the size of the smallest subset $X \subseteq E(G)$ such that $G\setminus X$ has no directed cycles, and let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices in $G$. In 2008, Chudnovsky, Seymour, and Sullivan showed that $\beta (G) \le \gamma(G)$, and conjectured that $\beta (G) \le \gamma(G)/2$. Recently, Dunkum, Hamburger, and P\'or proved that $\beta (G) \le 0.88 \gamma(G)$. In this note, we prove that $\beta (G) \le 0.8616 \gamma(G)$.

Affiliated with

Also associated with

No associations

Rating

On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564269