Harutyunyan's acyclic-set conjecture for planar oriented graphs

About 11 years old · traced to

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.

References

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.