pith. sign in

arxiv: 0909.2468 · v1 · submitted 2009-09-14 · 🧮 math.CO

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

classification 🧮 math.CO
keywords betagammacyclesdirectedchudnovskychudnovsky-seymour-sullivanconjectureconjectured
0
0 comments X p. Extension
read the original abstract

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)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.