[efyfabmr] map coloring the Voronoi diagram of equally spaced points on a sphere

pick one of the many methods for placing N "equally spaced" points on a sphere (e.g., Thomson problem, Tammes problem), compute the Voronoi partition, then map color, i.e., avoid adjacent regions of the same color.  (Lloyd's algorithm conveniently uses Voronoi to produce equally spaced points.)

4 colors suffice.  such a coloring might be pretty.  I suspect there will not be adjacent Voronoi regions with very short borders.  (maximizing the minimum Voronoi border segment could be another "equally spaced" metric.)

or, equally spaced points on the surface of any shape.  (the surface needs to have a definition for distance between any two points, a metric.  this might be related to a geodesic.)  if the shape is not topologically a sphere, then more than 4 colors might be required.  amazingly, the sufficient number is known for any number of holes in the donut (Heawood conjecture, no longer a conjecture, according to Wikipedia); the case of zero holes (the sphere or equivalently the plane) was the last to be proven.

colors = floor((7 + sqrt(1 + (48 * holes)))/2)

(there is a generalization of the formula that works if the surface has cross caps (real projective planes), e.g., Klein bottle.  such surfaces always self intersect in 3D space.  the classification theorem of surfaces then says that donut holes and cross caps are enough to topologically define any closed surface.)

is there a polynomial time algorithm that colors with the sufficient number of colors any map on a surface of any genus?

are random such coloring problems, the Voronoi diagrams of roughly equally spaced points, relatively easy to color?

how often can such maps on a sphere be 3-colored?  the regular hexagon tiling can be 3-colored.

there may be many ways to color the Voronoi partition, many more than just the 24 = 4! ways from permuting 4 colors.  how often does this happen?  if it does happen, how can we pick one of the colorings uniformly randomly?