And it turns out that on the Klein bottle, the maximum is 6 colors. More generally, this number depends directly on the number of holes of the surface [1].

[1]: https://en.wikipedia.org/wiki/Heawood_conjecture