Chudnovsky, Maria


Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $G$, we let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $\beta(G)$ be the size of the smallest \Def[feedback edge set]{feedback arc set}.

\begin{conjecture}If $G$ is a simple digraph without directed cycles of length $\le 3$, then $\beta(G) \le \frac{1}{2} \gamma(G)$. \end{conjecture}

Keywords: acyclic; digraph; feedback edge set; triangle free

Syndicate content