Theoretical Computer Science Asked on October 30, 2021
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.
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.
Answered by David Eppstein on October 30, 2021
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)
Answered by Xin Yuan Li on October 30, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP