## Acyclic partitions of planar digraphs

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.

References:[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

##### Revised: avgust 20, 2002.