pith. sign in

arxiv: 1504.06726 · v2 · pith:4JMUE3TDnew · submitted 2015-04-25 · 🧮 math.CO · cs.DM

Planar digraphs without large acyclic sets

classification 🧮 math.CO cs.DM
keywords acyclicdirectedplanaralbertsonbestconjecturecycledigraphs
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.