Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.