Algorithm
There exits a O(n) algorithm for 5-coloring a planar graphs by N. Chiba, T. Nishizeki, and N. Saito.
This algorithm is fairly complex so we examine a much easier O(n2) algorithm by Matula, Marble, and Isaacson.
Recursive-Smallest-Vertex-Degree-Last-Ordering-With-Interchange Coloring Algorithm
1. Order the vertices according to Smallest Vertex Ordering.
2. v1 is assigned color 1, this coloring <v1>
3. If <v1,…,vi-1> has been j colored using each of the colors 1,…,j and if m is the minimum positive integer not occurring on vertices of <v1,…,vi-1> adjacent to v in G then:
a. For m ≤ j, we assign each vertex of <v1,…,vi-1> the same color in <v1,…,vi>, and vi is assigned color m, thus j coloring <v1,…,vi>.
b. For m = j+1, let K Ì {1,..,j} be the set of color values such that α ε K implies exactly one vertex adjacent to vi in <v1,…,vi> has color α in <v1,…,vi-1>. If for some α,β Ì K, α≠β, an α,β component of <v1,…,vi-1> has only one vertex adjacent to to vi in <v1,…,vi>, then perform one α,β interchange on one such α,b component of <v1,…,vi-1>. Now color the vertices v1,…,vi-1 the same as in the new coloring of <v1,…,vi-1>, and vi with the available color, either α or β, and a j coloring of <v1,…,vi> is obtained; otherwise if no such interchange is possible, color v1,…,vi-1 the same as in <v1,…,vi-1>, and color vi with color j+1, thus (j+1) coloring <v1,…,vi>.
Complexity Analysis
Step 1: We can sort n vertices in O(nlogn).
Step 2: Constant time.
Step 3: We repeat step 3 (n-1) times. Each time, if we end up in condition 'a' it is easy to see that we do O(n) work. If we end up in condition 'b', we try to perform an α,β interchange. The check to see if we can do the interchange, takes linear time, and then interchange itself is also O(n). If we can't perform an α,β interchange then we just color v1,…,vi-1 the same as in <v1,…,vi-1>, and color vi with color j+1, which takes O(n). Therefore, step 3 has complexity: (n-1) * O(n) => O(n2).
Therefore, O(nlogn) + c + O(n2) => O(n2).