3
$\begingroup$

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: https://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph

  • 0
    if it makes the problem easier, this is equivalent to counting the homomorphims from your map/graph to $K_4$2011-04-04

1 Answers 1

2

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?

  • 0
    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?2011-04-07