We prove that the minimum weight of a dicycle is equal to the maximum number of disjoint dicycle covers, for every weighted digraph whose underlying graph is planar and does not have K_5 — e as a minor (K_5 — e is the complete graph on five vertices, minus one edge). Equality was previously known when forbidding K_4 as a minor, while an infinite number of weighted digraphs show that planarity does not guarantee equality. The result also improves upon results known for Woodall's Conjecture and the Edmonds-Giles Conjecture for packing dijoins. Our proof uses Wagner's characterization of planar 3-connected graphs that do not have K_5 — e as a minor.
展开▼
