An orientation $\overrightarrow{G}$ of an undirected graph $G$ is a directed graph obtained by assigning some direction on every edge of $G$.
An orientation $\overrightarrow{G}$ is said to be an Eulerian orientation if the number of in-neighbours of $v$ equals the number of out-neighbours of $v$ for every vertex $v$ of $\overrightarrow{G}$. Apparently, $G$ has an Eulerian orientation if and only if $G$ is an even-degree graph (i.e., every vertex of $G$ has even degree). In other words, a connected graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian (i.e., $G$ has an Euler tour).

Main definition: An orientation $\overrightarrow{G}$ is called a colourful Eulerian orientation if there is a vertex colouring $f$ of $\overrightarrow{G}$ such that the following hold for every vertex $v$ of $\overrightarrow{G}$ :

  • all in-neighbours of $v$ have the same colour, say colour $c_v$,
  • no out-neighbour of $v$ has colour $c_v$, and
  • no two out-neighbours of $v$ have the same colour.

(reminder: $f(u)\neq f(v)$ for every edge $uv$ of $G$ because $f$ is a vertex colouring of $\overrightarrow{G}$).

Are there graph classes where we can list all colourful Eulerian orientations in polynomial time?
We are optimistic on this front as opposed to listing Eulerian orientations. For instance, we know that if $G$ contains diamond or a circular ladder graph $CL_{2n+1}$ as a subgraph for some $n$, then $G$ cannot admit any colourful Eulerian orientation. We also know that if $\overrightarrow{G}$ is a colourful Eulerian orientation, then $\overrightarrow{G}$ orients every triangle ($C_3$) cyclically and orients every 4-vertex cycle ($C_4$) either cyclically or in 2-source 2-sink pattern (see figure below).


Disclaimer: This is a follow-up to an older question.

Thank you.


Your Answer

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

Browse other questions tagged or ask your own question.