2015/04/25 by Knauer, Kolja, Valicov, Petru, Wenger, Paul S. · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.06726
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 (n+1)/(2) \rceil, for any n. This disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.