10
$\begingroup$

Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient the edges of $G$ such that for each vertex $v$, there are no three consecutive edges (in the clockwise direction) such that all of them are oriented towards $v$ or all of them are oriented outwards from $v$. Does such orientation always exist?

$\endgroup$

1 Answer 1

10
$\begingroup$

Such an orientation always exists, here is a proof.

Take your 2-edge-connected graph $G$, and consider its dual graph $D$. $D$ has a proper 4-coloring in which each face of $D$ contains at most 3 different colors (add a vertex inside each face of $D$, connect it to all the vertices of the face, and apply the four color theorem to the resulting graph). Now, orient each edge of $D$ from the smaller color to the larger color. Note that there is no facial directed path on more that 2 edges in $D$ (otherwise, this would be a path with all 4 colors). Now, transfer the orientation of the edges of $D$ to the edges of $G$ in the natural way, and you get the desired result.

(in the first version of this post, the proof only gave that in 4-edge-connected plane graphs, you can find the desired orientation, and in 2-edge-connected plane graphs, you can find an orientation in which no four consecutive edges around a vertex have the same orientation)

$\endgroup$
1
  • $\begingroup$ I slightly modified the proof. Now you have the property that you need. $\endgroup$ Oct 11, 2018 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.