The Gallai-Younger conjecture for planar graphs (Q1375627): Difference between revisions

Younger conjectured that for every \(k\) there is a \(g(k)\) such that any digraph without \(k\) vertex disjoint cycles contains a set of at most \(g(k)\) vertices whose removal leaves an acyclic digraph. (This has previously been conjectured by Gallai for \(k=1\).) The authors prove this for planar digraphs. More recently the general conjecture has been resolved by Reed, Robertson, Seymour and Thomas.