Harutyunyan's acyclic-set conjecture for planar oriented graphs
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 . The conjecture is refuted by the paper's construction of oriented planar graphs whose maximum acyclic set has size at most .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.