2
$\begingroup$

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).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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), 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I have added a note to clarify what I mean. $\endgroup$
    – Cyriac Antony
    Jun 3, 2020 at 10:55
  • 2
    $\begingroup$ Ok, but 6-coloring is trivial and 5-coloring is easy, so what do you need the dual coloring for? $\endgroup$
    – David Eppstein
    Jun 3, 2020 at 18:55
  • $\begingroup$ 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) $\endgroup$
    – Cyriac Antony
    Jun 9, 2020 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.