<p><strong>Conjecture 1</strong>: Every 4-colourful Eulerian orientation of  is a good Eulerian orientation.<br />
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 <span class="math-container">$G$</span> (which is also claw-free) such that <span class="math-container">$G$</span> admits a 4-colourful Eulerian Orientation that is not good:
<a href="https://i.sstatic.net/yINO4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/yINO4.png" alt="enter image description here" /></a></p>
<p>We know that 4-CEOs of claw-free plane 4-regular graphs must orient every triangle (<span class="math-container">$C_3$</span>) and every rectangle (<span class="math-container">$C_4$</span>) cyclically. The graph <span class="math-container">$G$</span> in the above figure has vertex connectivity three.</p>
<p>Conjecture 1 might hold for the class of plane 4-regular claw-free graphs that are <strong>4-connected</strong>.</p>
<p>For the graph <span class="math-container">$G$</span> 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.</p>
<p><strong>Conjecture 2</strong>: A plane 4-regular claw-free 4-connected graph <span class="math-container">$H$</span> has a 4-CEO if and only if <span class="math-container">$H$</span> has a good 4-CEO.</p>

CC BY-SA 4.0
2022-01-01T02:23:30.723Z
2022-01-01T02:23:30.723Z
Cyriac Antony
<p>Let <span class="math-container">$G$</span> be a simple undirected <strong>plane 4-regular graph</strong>. Basic definitions are given at the bottom of this question.<br />
An Eulerian orientation of <span class="math-container">$G$</span> is <strong>good</strong> if for each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>, the edges around <span class="math-container">$v$</span> 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).<br />
<a href="https://i.sstatic.net/11M2H.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/11M2H.png" alt="enter image description here" /></a><br />
Figure 1: Good Eulerian orientations of a 12-vertex graph.</p>
<p>An Eulerian orientation of <span class="math-container">$G$</span> is a <strong><span class="math-container">$q$</span>-colourful Eulerian orientation</strong> (<span class="math-container">$q$</span>-CEO) if there exist a <span class="math-container">$q$</span>-vertex colouring <span class="math-container">$f$</span> of <span class="math-container">$G$</span> such that the following hold for each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>:</p>
<ul>
<li>both in-neighbours of <span class="math-container">$v$</span> get the same colour, say colour <span class="math-container">$c_v$</span>,</li>
<li>no out-neighbour of <span class="math-container">$v$</span> has colour <span class="math-container">$c_v$</span>, and</li>
<li>the out-neighbours of <span class="math-container">$v$</span> have different colours.</li>
</ul>
<p>(Of course, the colour of <span class="math-container">$v$</span> differs from its neighours because <span class="math-container">$f$</span> is a vertex colouring). See the figure below for an example.<br />
<a href="https://i.sstatic.net/vGKbZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vGKbZ.png" alt="enter image description here" /></a><br />
Figure 2: A 4-colourful Eulerian orientation (the colouring <span class="math-container">$f$</span> is also shown).</p>
<p>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 <span class="math-container">$q$</span>-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.</p>
<p><strong>I am trying to prove that every 4-colourful Eulerian orientation of <span class="math-container">$G$</span> is a good Eulerian orientation</strong> (I am not 100% sure of this; but, this surprisingly works for every example I know including members of two graph sequences).</p>
<p><strong>Proof attempts/approach</strong><br />
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 <span class="math-container">$H$</span> whose vertex set is the set of faces of <span class="math-container">$G$</span> whose boundaries are not directed cycles and <span class="math-container">$(F_1,F_2)$</span> is an arc in <span class="math-container">$H$</span> if the corresponding faces <span class="math-container">$F_1$</span> and <span class="math-container">$F_2$</span> in <span class="math-container">$G$</span> are<br />
as follows:
<a href="https://i.sstatic.net/GpvpU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GpvpU.png" alt="enter image description here" /></a>.<br />
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 <span class="math-container">$G$</span> has a 4-CEO, then (i) <span class="math-container">$G$</span> is 3-colourable, (ii) <span class="math-container">$G$</span> is <span class="math-container">$(\text{diamond},K_4)$</span>-free, and (iii) <span class="math-container">$|V(G)|$</span> is divisible by twelve. But, I am afraid these and other similar properties we know are not relevant to this question.</p>
<p><strong>Basic definitions</strong></p>
<ul>
<li>An <em>orientation</em> of <span class="math-container">$G$</span> is a directed graph obtained from <span class="math-container">$G$</span> by assigning some direction to each edge of <span class="math-container">$G$</span>.</li>
<li>An orientation of <span class="math-container">$G$</span> is an <em>Eulerian orientation</em> if every vertex of <span class="math-container">$G$</span> has 2 in-neighbours and 2 out-neighbours.</li>
</ul>
<p>[1] <em>Kawatani, Gen; Suzuki, Yusuke</em>, <a href="http://dx.doi.org/10.1007/s00373-020-02152-1" rel="nofollow noreferrer"><strong>Partially broken orientations of Eulerian plane graphs</strong></a>, Graphs Comb. 36, No. 3, 767-777 (2020). <a href="https://zbmath.org/?q=an:1439.05062" rel="nofollow noreferrer">ZBL1439.05062</a>.</p>

<graph-theory><planar-graphs><graph-colouring>
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
Cyriac Antony
# Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

(Asked by: username_0 on 2021-11-09)

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](https://i.sstatic.net/11M2H.png)](https://i.sstatic.net/11M2H.png)  
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](https://i.sstatic.net/vGKbZ.png)](https://i.sstatic.net/vGKbZ.png)  
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](https://i.sstatic.net/GpvpU.png)](https://i.sstatic.net/GpvpU.png).  
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**](http://dx.doi.org/10.1007/s00373-020-02152-1), Graphs Comb. 36, No. 3, 767-777 (2020). [ZBL1439.05062](https://zbmath.org/?q=an:1439.05062).

**Tags:** graph-theory, planar-graphs, graph-colouring


---

## 1 answers

### Answer by username_0 on 2022-01-01. Score: 1 | Accepted answer

**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](https://i.sstatic.net/yINO4.png)](https://i.sstatic.net/yINO4.png)

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.


---

