# Complexity of map coloring

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 [1]. What are the computational complexities to get face colorings for maps on other compact surfaces?

[1] 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.

-
I presume you've already seen this? – J. M. Nov 17 '11 at 9:47
Not yet. Great reference, thanks. – draks ... Nov 17 '11 at 11:57