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 has an acyclic set of size at least .
References
Status
- Refuted: Kolja Knauer, Petru Valicov, and Paul S. Wenger. Planar digraphs without large acyclic sets (arXiv, 2015) https://arxiv.org/abs/1504.06726
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.