<p>The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy to prove that duals of maximal planar graphs have 4-colorings (in fact 3-colorings except for <span class="math-container">$K_4$</span> by <a href="https://en.wikipedia.org/wiki/Brooks%27_theorem" rel="nofollow noreferrer">Brooks' theorem</a>), so if you could prove that a 3- or 4-coloring of the dual graph could always be converted into a 4-coloring of the primal graph then you would have also proved that a 4-coloring of the primal graph exists.</p>

<p>Perhaps there are more, but the only widely-accepted alternative proofs of the 4-color theorem reported by the Wikipedia article are the ones by Robertson, Sanders, Seymour, and Thomas (in connection with a faster algorithmic version of the theory) and Werner and Gonthier (in connection with a formalized proof in Coq). I think both are in roughly the same style of Appel and Haken, of proving that a reducible configuration exists, rather than using dual colorings.</p>

CC BY-SA 4.0
2020-06-03T10:55:08.440Z
Thank you for your answer. I have added a note to clarify what I mean.
Cyriac Antony
CC BY-SA 4.0
2020-06-03T18:55:25.090Z
Ok, but 6-coloring is trivial and 5-coloring is easy, so what do you need the dual coloring for?
David Eppstein
CC BY-SA 4.0
2020-06-09T02:40:08.020Z
The dual coloring may have interesting properties w.r.t. colouring varaints. For example, Tait's edge colouring scheme gives a one-one correspondence between 4-acyclic colourings of maximal planar graphs $G$ and Hamiltonian 3-covers of dual of $G$. (A graph has a Hamilonian 3-cover if it has 3 Hamiltonian cycles such that each edge of the graph occur in exactly two of those cycles)
Cyriac Antony
CC BY-SA 4.0
2020-06-03T04:33:19.237Z
2020-06-03T04:33:19.237Z
David Eppstein
<p>A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one correspondence between 4-colourings of maximal planar graphs and 3-edge colourings of their dual graphs. That is, given a 4-vertex colouring of a maximal planar graph <span class="math-container">$G$</span>, one can produce a 3-edge colouring of the dual graph <span class="math-container">$G^*$</span> of <span class="math-container">$G$</span>, and vice versa. The schemes to produce one from the other are elegant.</p>

<p>Similarly, there are schemes to produce (vertex) colouring of <span class="math-container">$G^*$</span> from colouring of <span class="math-container">$G$</span>.</p>

<p><strong>Is there a known scheme to produce a colouring of a maximal planar graph from a colouring of its dual graph?</strong><br>
(In other words, given a face colouring of a maximal planar graph, can we produce a vertex colouring?)</p>

<p>Clarification: I am not asking for a 4-colouring of the maximal planar graph. From a 4-colouring (or 5-coluoring) of its dual graph, is it possible to produce a colouring of the maximal planar graph (may be with 5 or even 6 colours; but <em>it should be a colouring scheme</em> that actually use the colouring of the dual graph).</p>

<planar-graphs><graph-colouring>
Producing colouring of maximal planar graphs G from colouring of dual of G
Cyriac Antony
# Producing colouring of maximal planar graphs G from colouring of dual of G

(Asked by: username_0 on 2020-06-03)

A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one correspondence between 4-colourings of maximal planar graphs and 3-edge colourings of their dual graphs. That is, given a 4-vertex colouring of a maximal planar graph $G$, one can produce a 3-edge colouring of the dual graph $G^\*$ of $G$, and vice versa. The schemes to produce one from the other are elegant.

Similarly, there are schemes to produce (vertex) colouring of $G^\*$ from colouring of $G$.

**Is there a known scheme to produce a colouring of a maximal planar graph from a colouring of its dual graph?**  
(In other words, given a face colouring of a maximal planar graph, can we produce a vertex colouring?)

Clarification: I am not asking for a 4-colouring of the maximal planar graph. From a 4-colouring (or 5-coluoring) of its dual graph, is it possible to produce a colouring of the maximal planar graph (may be with 5 or even 6 colours; but *it should be a colouring scheme* that actually use the colouring of the dual graph).

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


---

## 1 answers

### Answer by username_1 on 2020-06-03. Score: 4

The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy to prove that duals of maximal planar graphs have 4-colorings (in fact 3-colorings except for $K\_4$ by [Brooks' theorem](https://en.wikipedia.org/wiki/Brooks%27_theorem)), so if you could prove that a 3- or 4-coloring of the dual graph could always be converted into a 4-coloring of the primal graph then you would have also proved that a 4-coloring of the primal graph exists.

Perhaps there are more, but the only widely-accepted alternative proofs of the 4-color theorem reported by the Wikipedia article are the ones by Robertson, Sanders, Seymour, and Thomas (in connection with a faster algorithmic version of the theory) and Werner and Gonthier (in connection with a formalized proof in Coq). I think both are in roughly the same style of Appel and Haken, of proving that a reducible configuration exists, rather than using dual colorings.

> **Comments:**
> **username_0**: Thank you for your answer. I have added a note to clarify what I mean.  
> **username_1**: Ok, but 6-coloring is trivial and 5-coloring is easy, so what do you need the dual coloring for?  
> **username_0**: The dual coloring may have interesting properties w.r.t. colouring varaints. For example, Tait's edge colouring scheme gives a one-one correspondence between 4-acyclic colourings of maximal planar graphs $G$ and Hamiltonian 3-covers of dual of $G$. (A graph has a Hamilonian 3-cover if it has 3 Hamiltonian cycles such that each edge of the graph occur in exactly two of those cycles)  

---

