An efficient algorithm to decide if a triangulation is 3-colourable
Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces.

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.

This algorithm is very similar to the one for deciding whether a given graph can be 2-colored.