4
$\begingroup$

The following paragraph is from this answer by David Eppstein (emphasis mine).

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

(A maximal planar graph is a graph with a planar embedding such that every face is a triangle).

I don't quite understand how emphasized part works as a proof. Let $G$ be a maximal planar graph. If $G$ is 3-colourable, then the 3-colouring is unique (upto swapping of colours) because in every diamond subgraph of $G$, both degree-2 vertices of the subgraph should get the same colour. I suppose this suggests an algorithmic method for testing 3-colourability of $G$ namely (i) pick a triangle, (ii) give a 3-colouring to it arbitrarily, (iii) repeatedly extend it to adjacent triangles (assuming there is no inconsistency), and (iv) finally verify that the assignment is indeed a 3-colouring. If there is a vertex of odd degree, we will not succeed in assigning colour to all vertices. My question is this:- How can we guarantee that the assignment will be consistent provided all vertices have even degree?

Note: I don't see how Eulerian property (aka all vertices having even degree) ensures consistency of the assignment. I am asking this as a new question rather than a comment to the linked answer because he was answering a different question.

$\endgroup$
3
$\begingroup$

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then propagate information around the cycle you come back to something different.

If you have a dual cycle that surrounds only a single primal vertex, then it's a wheel, and it's inconsistent if and only if it's an odd wheel.

If you have a dual cycle that surrounds more than one primal vertex, you can draw a dual path inside it that splits it into two dual cycles that each surround fewer primal vertices (this is where we use the fact that the triangulation is on the plane and not on a higher-genus surface). If both smaller cycles are consistent you could glue together consistent colorings of both to get a consistent coloring of the whole thing. So by induction on number of primal vertices contained, when the graph is Eulerian, all dual cycles are consistent.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. Of course, it was obvious to you, but not to me. I thought you did not give details because you were giving a known result and a short proof for it; but I could not trace how it worked. $\endgroup$ – Cyriac Antony Jul 19 at 5:42
  • 1
    $\begingroup$ Well, it is a known result at least. For instance it's an exercise in Bondy & Murty, Graph Theory with Applications (1976), p. 159. I don't remember my exact intent when I wrote that answer 10 years ago but it looks more like a description of the construction of a 3-coloring than a proof that the construction works. $\endgroup$ – David Eppstein Jul 20 at 7:46
0
$\begingroup$

The key here is to note that the planar graph considered is maximal. Every vertex in this graph is adjacent to a triangle since every face of the graph is a triangle. Thus this is possible to extend the coloring on one triangle to the coloring of the entire graph since fixing two colors of the triangle forces the color on the third vertex. (Maybe look at this link for a similar response: https://math.stackexchange.com/questions/449811/planar-graph-with-maximum-number-of-edges-and-3-colouring-in-eulerian)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. But, I am aware of this. I am asking how this serves as a proof that a 3-colouring is possible. $\endgroup$ – Cyriac Antony Jul 19 at 5:39

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.