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.
Submitted by: Dan Archdeacon (with thanks to F. Bruce Shepherd of
Bell Labs and to Doug Woodall)
Send comments to email@example.com