4
$\begingroup$

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 ?

Improve this question
$\endgroup$
5
  • $\begingroup$ @M.Winter The edges are oriented alternately forward and backward, except that the last edge is unspecified. $\endgroup$
    – Brendan McKay
    Commented Sep 4, 2019 at 10:18
  • $\begingroup$ Do you have an example of a graph for which you know that such an orientation does not exist? $\endgroup$
    – M. Winter
    Commented Sep 4, 2019 at 13:20
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Sep 4, 2019 at 15:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – LeechLattice
    Commented Sep 4, 2019 at 16:24
  • $\begingroup$ Thank you for your answers! It seems to be a rather limited class of graphs then. $\endgroup$
    – Thomas Haettel
    Commented Sep 6, 2019 at 12:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .