# Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

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.

This is the conjecture made in the question. We now have a counter-example to Conjecture 1. That is, we have an example of a plane 4-regular graph $$G$$ (which is also claw-free) such that $$G$$ admits a 4-colourful Eulerian Orientation that is not good:
We know that 4-CEOs of claw-free plane 4-regular graphs must orient every triangle ($$C_3$$) and every rectangle ($$C_4$$) cyclically. The graph $$G$$ in the above figure has vertex connectivity three.
For the graph $$G$$ in the above figure, the good Eulerian orientations are also 4-CEOs. This suggests the next conjecture which is a very relaxed form of Conjecture 1 for a subclass.
Conjecture 2: A plane 4-regular claw-free 4-connected graph $$H$$ has a 4-CEO if and only if $$H$$ has a good 4-CEO.