# How many different four coloring exist for a given regular map?

Excluding maps that can be colored with 2 or 3 colors, how many different four coloring exist for a given regular map?

Naturally, two identical maps have to be regarded as differently colored if the same coloring cannot be obtained by swapping colors inside one of the two maps. It is also intended that the two maps used the same set of four colors.

Is there a paper on this? Someone has already studied this?

UPDATE: If someone is interested I opened the same question on mathoverflow: here is the link to the same question: http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph

-
if it makes the problem easier, this is equivalent to counting the homomorphims from your map/graph to $K_4$ –  Harry Stern Apr 4 '11 at 1:10

You may have to be more specific about what you're after, because the answer is that it varies almost arbitrarily from graph to graph. It's easy to see that there are four-colorable graphs with exponentially-many distinct colorings; just string together copies of $K_4$ and the colors of the vertices not in the chain are arbitrary, leading to at least $2^n$ colorings of a $4n$-node graph. It's not much harder to see that there are 4-colorable graphs of arbitrary size with unique colorings, and in general counting the number of 4-colorings for an arbitrary graph is #P-complete. Can you say a bit more about what you're after particularly?