Erdős Problem #1006 — Acyclic orientations robust under reversing one edge
If a graph has girth greater than , can its edges always be oriented so that the orientation contains no directed cycle and no cycle becomes directed after reversing the orientation of a single edge?
References
Additional references
P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.
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.