# An efficient algorithm to decide if a triangulation is 3-colourable

Design an efficient algorithm to decide whether a given triangulation with $n$ points is $3$-colourable. The triangulation is given by a sorted edge list, where every edge is given by the indices of its two end points. Further, for every edge there are given the indices of the points with which the edge forms a triangle in the triangulation (two indices for interior edges and one index for edges on the boundary of the convex hull). Give proof for the correctnesss of your algortihm.

Below is an example.

I've heard about the BFS and DFS algorithms in lecture, but I don't see how I could apply this here. I'd be thankful for any help.

• @YuvalFilmus Not necessarily, every triangle must be colored with at least 3 different colours and it doesn't seem so far-fetched that 3 colours suffice unless we can find some obvious counter-example (such as in the picture). Plus, the exercise implies that it lies in P, so I'd bet there's some trick here. – Discrete lizard Jan 15 '18 at 17:39
• Deciding whether a planar graph is 3-colorable is NP-hard. This is quite close to the problem at hand. – Yuval Filmus Jan 15 '18 at 17:40
• Is this a homework problem? Academia.SE has had a bunch of questions about that recently. – dalearn Jan 16 '18 at 0:38
• Yes it is, but I couldn't find anything similiar to this exercise. – 3nondatur Jan 16 '18 at 6:47

Pick an arbitrary triangular face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex of $F'$. Continuing in this way, attempt to color all vertices. If you're successful, the graph can be 3-colored. Otherwise, the graph cannot be 3-colored.
• You don't. You start with an arbitrary triangle (which you can find by picking a vertex and going over all pairs of neighbors), and then you repeatedly locate a vertex which forms a triangle with two of the vertices of the current triangle. This algorithm runs in time $O(n^2)$. Using more sophisticated approaches you can probably go down to $\tilde{O}(n)$. – Yuval Filmus Jan 16 '18 at 7:58