# Edge orientation of finite triangle-free graphs

Given a finite simple graph without triangles, I am interested in conditions ensuring that there exists an orientation of the edges such that the following holds.

There exists no cycle $$x_0,x_1,\dots,x_{2p},x_0$$ of odd length such that for each $$0 \leq i \leq p-1$$, both edges $$[x_{2i},x_{2i+1}]$$ and $$[x_{2i+1},x_{2i+2}]$$ are oriented towards $$x_{2i+1}$$.

If there is no cycle of odd length at all, any orientation works. If the graph is $$3$$-colourable, one can also easily find such an orientation. Are there more general conditions on the graph to ensure the existence of such an orientation ?

• @M.Winter The edges are oriented alternately forward and backward, except that the last edge is unspecified. Sep 4 '19 at 10:18
• Do you have an example of a graph for which you know that such an orientation does not exist? Sep 4 '19 at 13:20
• 3-colourable graphs have a homomorphism onto a triangle. In general, graphs with a homomorphism onto any cycle are examples, with the same proof. Even more generally, if $G$ is an example, anything which has a homomorphism onto $G$ is an example too. Sep 4 '19 at 15:15
• @M.Winter The induced subgraph formed by all vertices with distance 2 to a chosen vertex in Hoffman-Singleton does not have such an orientation. And neither does the Wong graph. Both are comfirmed by SAT solvers. Sep 4 '19 at 16:24
• Thank you for your answers! It seems to be a rather limited class of graphs then. Sep 6 '19 at 12:35