In 2001, Škrekovski proposed the following conjecture (see [1]):
Conjecture (Škrekovski): Let G be a simple planar graph, and let D be a digraph obtained from G by orienting all of its edges. Then V(D) can be partitioned into two sets such that the subdigraph induced on any of these sets is acyclic.
This conjecture is related to the notion of the chromatic number of a digraph introduced in [1]. Any counterexample to this conjecture would be quite complicated since the vertices of small planar graphs can always be partitioned into two sets whose induced subgraphs are forests.
Mike Albertson (private communication) asked the following easier question:
Problem: Is it true that every planar digraph contains a subset of at least half of the vertices such that the subdigraph induced on this subset is acyclic?
For some additional information see also the August 2002 Problem of the month.
[1] D. Bokal, G. Fijavž, M. Juvan, P. M. Kayll, B. Mohar, The circular chromatic number of a digraph, preprint, 2002.
Send comments to Bojan.Mohar@uni-lj.si