Revision history of
1006. All highlighted changes are compared to the current version.
Current version
Let $G$ be a graph with girth $>4$ (that is, it contains no cycles of length $3$ or $4$). Can the edges of $G$ always be directed such that there is no directed cycle, and reversing the direction of any edge also creates no directed cycle?
In
[Er71] Erdős credits this problem to Ore, who gave an example of a graph without this property which has girth $4$. Gallai noted that the
Grötzsch graph also lacks this property.
This is false - Nešetřil and Rödl
[NeRo78b] proved that, for every integer $g$, there is a graph $G$ with girth $g$ such that every orientation of the edges in $G$ contains a directed cycle or a cycle obtained from a directed cycle by reversing one directed edge.
2025-10-20 00:00:00
Let $G$ be a graph with girth $>4$ (that is, it contains no cycles of length $3$ or $4$). Can the edges of $G$ always be directed such that there is no directed cycle, and reversing the direction of any edge also creates no directed cycle?
In
[Er71] Erdős credits this problem to Ore, who gave an example of a graph without this property which has girth $4$. Gallai noted that the
Gr\"{otzsch graph} also lacks this property.
This is false - Nešetřil and R\"{o}dl
[NeRo78b] proved that, for every integer $g$, there is a graph $G$ with girth $g$ such that every orientation of the edges in $G$ contains a directed cycle of.
