
acyclic
Non-edges vs. feedback edge sets in digraphs ★★★
Author(s): Chudnovsky; Seymour; Sullivan
For any simple digraph , we let
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and
be the size of the smallest feedback edge set.
Conjecture If
is a simple digraph without directed cycles of length
, then
.



Keywords: acyclic; digraph; feedback edge set; triangle free
The Two Color Conjecture ★★
Author(s): Neumann-Lara
Conjecture If
is an orientation of a simple planar graph, then there is a partition of
into
so that the graph induced by
is acyclic for
.





