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

The Two Color Conjecture ★★

Author(s): Neumann-Lara

\begin{conjecture} If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$. \end{conjecture}

Keywords: acyclic; digraph; planar

Syndicate content