**
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(n^{2}) 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. v_{1}
is assigned color 1, this coloring <v_{1}>

3. If
<v_{1},…,v_{i-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 <v_{1},…,v_{i-1}>
adjacent to v in G then:

a.
For m ≤ j, we
assign each vertex of <v_{1},…,v_{i-1}>
the same color in <v_{1},…,v_{i}>,
and v_{i}
is assigned color m, thus j coloring <v_{1},…,v_{i}>.

b.
For m = j+1, let K
Ì
{1,..,j} be the set of color values such
that α
ε
K implies exactly one vertex adjacent to v_{i}
in <v_{1},…,v_{i}>
has color
α
in <v_{1},…,v_{i-1}>.
If for some
α,β
Ì
K, α≠β,
an
α,β
component of <v_{1},…,v_{i-1}>
has only one vertex adjacent to to v_{i}
in <v_{1},…,v_{i}>,
then perform one
α,β
interchange on one such
α,b
component of <v_{1},…,v_{i-1}>.
Now color the vertices v_{1},…,v_{i-1}
the same as in the new coloring of <v_{1},…,v_{i-1}>,
and v_{i} with the available color, either
α
or β,
and a j coloring of <v_{1},…,v_{i}>
is obtained; otherwise if no such interchange is possible, color v_{1},…,v_{i-1}
the same as in <v_{1},…,v_{i-1}>,
and color v_{i}
with color j+1, thus (j+1) coloring <v_{1},…,v_{i}>.

__
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 v_{1},…,v_{i-1}
the same as in <v_{1},…,v_{i-1}>,
and color v_{i}
with color j+1, which takes O(n). Therefore, step 3 has complexity: (n-1)
* O(n) => O(n^{2}).

**
Therefore, O(nlogn) + c +
O(n ^{2}) => O(n^{2}).**