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.

The conjecture is unknown even in the case k = 3.

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.

  Does there exist a constant k such that if every dicut is of size at most k, then there exist 2 disjoint dijoins?

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

Send comments to

November, 2003