Planar digraphs without large acyclic sets

Abstract

Given a directed graph, an acyclic set is a set of vertices inducing a subgraph with no directed cycle. In this note we show that there exist oriented planar graphs of order $n$ for which the size of the maximum acyclic set is at most $\lceil \frac{n+1}{2}\rceil$, for any $n$. This disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.

3 pages, 1 figure