Hefetz's acyclic-set conjecture for planar digraphs
Hefetz's acyclic-set conjecture for planar digraphs
Let be a simple planar digraph on vertices. An acyclic set is a vertex set inducing no directed cycle in . Hefetz's conjecture. Every simple -vertex planar digraph has an acyclic set of size at least
The conjecture is cited as supporting evidence for the broader 2-colorability problem, but no resolution is given in the source.
Sources & referencesView supporting material
Primary source
Ararat Harutyunyan and Bojan Mohar, “Planar digraphs of digirth five are 2-colorable”, arXiv:1401.2213 (2014).
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
Sign in to submit a solution.
No solutions have been posted yet.