A lot of this work depends on list coloring.

Here is the Graph List Coloring problem: Given a graph G and, for each

vertex v a list of colors L(v), can you color G where v is colored with

some vertex in L(v). A graph is k-choosable if it is list-colorable where

each L(v) is a subset of {1,…,k}

On two short proof about list coloring graphs by Nancy Eaton (2003)

On two short proofs about list coloring graphs II by Nancy Eaton (2003)

Every planar graph is 5-choosable by Carsten Thomassen (1994)

If we are going to look at graphs of genus g we need to find the genus of a graph. Hence we need this paper:

A simpler linear time algorithm for embedding graphs into an arbitraray surface and the genus of graphs of bounded tree-width by Kawarabayashi, Mohar, Reed (2009). This paper shows how you can check if G has genus g in O(gn) time.

Papers on 5-colorability

A five-color theorem for graphs on surfaces by Hutchinson (1984). This paper shows that if a graph has certain properties then it is 5-colorable.

Five-coloring graphs on the torus by Caarsten Thomassen (1993). This paper shows that 5-colorable restriced to the torus (genus 1) is in P.

Color-Critical graphs on a fixed surface by Thomassen. This paper shows that the problems of 5-colorability for fixed genus g graphs is in P. No algorithm is given

List-coloring embedded graphs by Dvorak and Kawarabayashi (2012. This paper sgive an algorithm for determining, given a graph of fixed genus g with girth at least 5, is it 3-list colorable. They claim it can be extended to 5-list coloring.

by Postle (2019). This paper gives a deterministic distributed algorithms for 5-coloring planar graphs in polylog time.