Abstract
Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG−X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Gallai: Problem 6,Theory of Graphs, Proc. Col. Tihany, 1968, 362.
B.Bollobás: Graphs without two independent circuits (Hungarian),K. Mat. Lapok,15 (1964), 311–321.
C. Hoang andB. Reed: A Note on Short Cycles in Digraphs,Journal of Combinatorial Theory (B),66 (1987), 103–107.
W. McCuaig: Intercyclic Digraphs,Graph Structure Theory, Contemporary Mathematics147 (1993), 203–246.
Alice Metzlar andU. S. R. Murty: Disjoint Circuits in Planar Digraphs,Manuscript, 1991.
P. Seymour: Fractionally Packing Disjoint Circuits,Combinatorica, to appear.
C. Thomassen: Disjoint Cycles in Digraphs,Combinatorica,14 (1983), 393–396.
Thurston: The geometry and topology of three-manifoldsunpublished.
D. Younger: Graphs with interlinked directed circuits,Proceedings of the Midwest Symposium on Circuit Theory 2, (1973), XVI 2.1-XVI 2.7.