There is a linear time algorithm to 5-color a planar graph: see Wikipedia.
I have implemented my under active development planar_graph_playground. The undirected graph library is implemented in NodeJS, Python and C++. Algorithms mostly look the same (design goal), using anonymous functions in NodeJS, lambdas in Python and C++ lambdas which are a bit different.
I have implemented a simple 6-coloring algorithm, and there are big sample graphs in the repo. On Intel i7 python you get 6-coloring in 1.5s/17.5s of the faces of a maximal planar graph (the vertices of its dual graph) for 10,000 / 100,000 vertices graphs:
$ time ( ./rpy python_6coloring.py ../graphs/10000.a > out )
real 0m1.449s
user 0m1.517s
sys 0m0.190s
$ time ( ./rpy python_6coloring.py ../graphs/100000.a > out )
real 0m17.446s
user 0m17.187s
sys 0m0.586s
$
Same algorithm in C++ 6-colors 100,000 / 500,000 vertices maximal planar graph faces in 9.7s/20.7s:
$ time (./c++_6coloring ../graphs/500000.a > out )
real 0m9.770s
user 0m9.606s
sys 0m0.163s
$ time (./c++_6coloring ../graphs/1000000.a > out )
real 0m20.772s
user 0m20.410s
sys 0m0.365s
$