**Cuts in
Digraphs and Woodall's Conjecture**

Let D be a directed graph.
A feedback arc-set of D is a set of arcs A such that D-A has no directed cycles.The name
comes from the fact that any walk will eventually use an edge of A. A special case of Woodall's
conjecture is the following:

**Conjecture:*** If *D* is a planar digraph with no
directed cycle of length less than *k*, then the arcs of *D*
can be partitioned into *k* feedback arc sets. *

A dicut is a set of arcs A such that every directed cycle contains an arc from A. A dijoin is a set of arcs that hit all dicuts.

Question:

Submitted by: Dan Archdeacon (with thanks to F. Bruce Shepherd of
Bell Labs and to Doug Woodall)

Send comments to *dan.archdeacon@uvm.edu*

November, 2003