Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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.