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).
enter image description here
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.
enter image description here
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: enter image description here.
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.


Conjecture 1: Every 4-colourful Eulerian orientation of 𝐺 is a good Eulerian orientation.
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: enter image description here

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.

Conjecture 1 might hold for the class of plane 4-regular claw-free graphs that are 4-connected.

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.


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.