Originator: Michael Albertson (presented by D. West - REGS 2008; also in REGS 2006?)
Definitions: An oriented planar graph is an orientation of a planar graph. An acyclic digraph is a digraph having no cycle (in the directed sense).
Background: A number of long-standing conjectures concern the largest (number of vertices) induced subgraph of a (possibly restricted) planar graph that is a forest (possibly of a restricted type). For example, it is conjectured that every planar graph has an induced forest with at least half the vertices (Albertson-Berman) and an induced linear forest with at least 4/9 of the vertices (Chappell), and it is conjectured that every bipartite graph has an induced forest with at least 5/8 of the vertices. A presentation of these conjectures and partial results on them appears here. The problem now is to consider analogues for oriented planar graphs.
Question: What is the maximum c such that every oriented planar graph with n vertices has an induced acyclic subdigraph with at least cn vertices? Similarly, what is the maximum guarantee for oriented bipartite planar digraphs.
Comments: Since an oriented graph has no more (and generally fewer) cycles than the underlying undirected graph, the ratios that can be guaranteed in the directed versions of the problem should be larger than in the undirected versions.
For the main question about forests in planar graphs, no more than n/2 vertices can be guaranteed. Albertson presented a planar graph in which the independence number is only n/4; draw (n/4)C4 as concentric 4-cycles, and add an 8-cycle on the vertices of each two neighboring 4-cycles, embedded in the region between them (an additional chord can be added in the innermost and outermost faces). For the directed analogue, also no more than ⌈n/4⌉ can be guaranteed. Wenger constructed a sequence of planar digraphs in which the number n of vertices is odd and the minimum number of vertices that must be deleted to break all cycles is ⌊n/2⌋.
Borodin's result that planar graphs can be 5-colored so that every two color classes together induce an acyclic subgraph implies that at least 2n/5 vertices can be guaranteed. In the directed version, no lower bound stronger than this 2n/5 has been given, even though the answer to the digraph problem must be at least as large as the answer to the undirected problem.
References:
See here for the undirected
problems and their references.