There is a linear time algorithm to 5-color a planar graph:
[enter link description here][1]

I have implemented my under active development planar_graph_playground:
[enter link description here][2]
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 6-colors 100,000 / 500,000 vertices maximal planar graph faces in 9.7s/20.7s.

  [1]: https://en.wikipedia.org/wiki/Five_color_theorem#Linear_time_five-coloring_algorithm
  [2]: https://github.com/Hermann-SW/planar_graph_playground