Harutyunyan's acyclic-set conjecture for planar oriented graphs

Let an oriented graph be a digraph without loops and multiple arcs, and let an acyclic set be a set of vertices inducing a subgraph with no directed cycles. Harutyunyan's conjecture. Every planar oriented graph of order nn has an acyclic set of size at least 3n5\frac{3n}{5}. The conjecture is refuted by the paper's construction of oriented planar graphs whose maximum acyclic set has size at most n+12\lceil \frac{n+1}{2} \rceil.

Sources & referencesView supporting material

Primary source

Kolja Knauer, Petru Valicov and Paul S. Wenger, “Planar digraphs without large acyclic sets”, arXiv:1504.06726 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.