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

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:

share|cite|improve this question
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
up vote 2 down vote accepted

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?

share|cite|improve this answer
For what I'm trying to analyze, K4 has to be regarded as having just one possible coloring. In your K4 example, after the graph has been colored, through subsequent exchanges of colors, each K4 copy can be converted to any other. See this picture: In other words, since when coloring K4 vertexes, colors can be choosen arbitrarily, any four coloring is equivalent. For more complex maps swapping colors won't help. I'd like to understand how this is related to the shape of the map. I want to add this tool to my java application. – Mario Stefanutti Apr 4 '11 at 21:39
In other words, for example, for maps with hundreds of faces, once a map has been properly four colored, I don't want to count all other colorings that derive from subsequent exchanges of colors. My doubt is how many "different" (in the meaning I explained) coloring exist for a given map? Is there a study on this that can help me? – Mario Stefanutti Apr 7 '11 at 8:51

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.