Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question.
An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around $v$ in the cyclic order alternate between in-edges and out-edges. Every plane Eulerian graph admits exactly two good Eulerian orientations, namely those induced by 2-face colouring (see the figure below).
Figure 1: Good Eulerian orientations of a 12-vertex graph.
An Eulerian orientation of $G$ is a $q$-colourful Eulerian orientation ($q$-CEO) if there exist a $q$-vertex colouring $f$ of $G$ such that the following hold for each vertex $v$ of $G$:
- both in-neighbours of $v$ get the same colour, say colour $c_v$,
- no out-neighbour of $v$ has colour $c_v$, and
- the out-neighbours of $v$ have different colours.
(Of course, the colour of $v$ differs from its neighours because $f$ is a vertex colouring). See the figure below for an example.
Figure 2: A 4-colourful Eulerian orientation (the colouring $f$ is also shown).
For the graph in the figures, every 4-colourful Eulerian orientation is a good orientation (e.g., the orientation in Figure 2 is same as Figure 1b); this graph has four $q$-CEOs two of which are 4-CEOs and the rest are 6-CEOs. The two 4-CEOs of this graph are good whereas the two 6-CEOs are not.
I am trying to prove that every 4-colourful Eulerian orientation of $G$ is a good Eulerian orientation (I am not 100% sure of this; but, this surprisingly works for every example I know including members of two graph sequences).
Proof attempts/approach
Proof by cases does not seem to be the way to go. I have considered a number of associated graphs such as dual graph and radial graph (the radial graph played a major role in a relaxed version of good Eulerian orientation [1]). Another associated graph I have considered is the plane Eulerian digraph $H$ whose vertex set is the set of faces of $G$ whose boundaries are not directed cycles and $(F_1,F_2)$ is an arc in $H$ if the corresponding faces $F_1$ and $F_2$ in $G$ are
as follows:
.
Unfortunately, I couldn't find any connection to these associated graphs. By the way, we know several properties of 4-regular graphs that admit a 4-CEO. For instance, if a 4-regular graph $G$ has a 4-CEO, then (i) $G$ is 3-colourable, (ii) $G$ is $(\text{diamond},K_4)$-free, and (iii) $|V(G)|$ is divisible by twelve. But, I am afraid these and other similar properties we know are not relevant to this question.
Basic definitions
- An orientation of $G$ is a directed graph obtained from $G$ by assigning some direction to each edge of $G$.
- An orientation of $G$ is an Eulerian orientation if every vertex of $G$ has 2 in-neighbours and 2 out-neighbours.
[1] Kawatani, Gen; Suzuki, Yusuke, Partially broken orientations of Eulerian plane graphs, Graphs Comb. 36, No. 3, 767-777 (2020). ZBL1439.05062.