This is a follow up question to this one.
I've recently read that for planar maps, it is possible to color these in $O(N^2)$, $N$ being that number of vertices . What are the computational complexities to get face colorings for maps on other comapct surfaces?
 Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proc. 28th Symposium on Theory of Computing, pages 571-575. ACM, 1996.