How many "different" colorings (excluding exchanges) exist for a given map (graph)? In particular I'm interested in regular maps, excluding all maps that can be colored with 2 or 3 colors.
For what I need to analyze, maps have to be regarded as differently colored, if the same coloring cannot be obtained by subsequent exchanges of colors.
In other words, for example, once a map has been properly colored, I don't want to count all other configurations that derive from subsequent exchanges of colors.
Since the arbitrary nature of choosing colors, these derived configurations are equivalent (for what I'm analyzing) to the first one, since they could have been obtained just choosing different colors in the first place. Instead, there are colorings that differ in such a way that exchanging colors won't help to transform one configuration into the other.
In the following picture the graphs named (A) and (B) are the only ones that cannot be converted into one another by swapping colors.
    
 (source)
My question is: how many "different" colorings (in the meaning I explained) exist for a given map?
I've only found an article on http://en.wikipedia.org/wiki/Graph_coloring that count all possible colorings including swaps.
Is there a paper that can help me on this?
I already posted this to math.stackexchange but, so far, I haven't received the answer I was looking for.
 A: As a youthful folly I once wrote a paper "On the algebra of the four color problem", Ens. Math 11 (1965), 175-193. It can be found here:
https://people.math.ethz.ch/~blatter/fourcolor.pdf
In this paper the permutations of colors are systematically "quotiented out" via a certain homological process.
A: Counting the number of 4-colorings (or indeed, $k$-colorings for any fixed $k\ge3$) of a planar graph is a $\#P$-complete problem (as proved by Vertigan), hence it (presumably) cannot be computed by any algorithm significantly more efficient than a brute-force search.
A: Computer experiments yield some interesting numbers.  The following numbers do not rule out the maps that are 3-colorable.  Without thinking too deeply, my guess is that the number that would be ruled out would be extremely small, but this is only a guess.
Under reasonable restrictions (valance three on all vertices, regions intersect in connected sets, sufficient connectivity, etc.) the number of such colorings is not large for numbers of regions where computation is feasible.  For 12 regions (the current limit of our computations and patience), the maximum number of colorings is 172.  The minimum, of course is 1.  However, the second to largest number of colorings for 12 regions is 92.  Then comes 85, then 84, then 76, then 64 and so forth.  The smallest number of colorings that never appears with 12 regions is a highly suggestive 31.
For 11 regions, the maximum is 85, then 48, then 44, then 41, then 40, then 29, ...  The smallest number not to appear with 11 regions is an equally suggestive 15.
If one starts to suspect a pattern, the smallest number not to appear with 10 regions is 10.  With 10 regions the maximum is 44, then 28, then 21, then 20, etc.
The estimated time to work with 13 regions with the current program is one month.  It could definitely be made faster, but 14, 15, 16 regions are definitely out of reach.
For the curious, the number of graphs investigated with 12 regions was 27360612.  Certain obvious symmetries were not used to cut down the number but it is not clear how much the cut down would have been.  Nothing beyond a factor of (somewhat less than) two was obvious.
Note that the assumption that regions intersect in connected sets is a large assumption.  Without that assumption, the number of colorings would explode.
Bottom line: I too would be interested in any information about the total number (now known to always be at least one) of colorings, modulo permutations of the colors, for planar graphs.
A: Are you looking for a polynomial time solution? If not, you can find the number of colorings of the graph with n colors and divide it by n! to get the number of different colorings as you defined above. One way to find the number of colorings for each n would be to find the chromatic polynomial.
http://en.wikipedia.org/wiki/Chromatic_polynomial
A: How many colors do you want to have?  I felt the question was ambiguous.  If you want to have an arbitrarily fixed number of colors available, or if you want to have an arbitrarily fixed number of colors actually used, you will be computing something equivalent to the chromatic polynomial.  If you want only 4 colors, or only 5 colors, the problem need not be equivalent to the chromatic polynomial.
I disagree with Emil Jerábek's statement that the number "(presumably) cannot be computed by any algorithm significantly more efficient than a brute-force search."  It depends on what you mean by "significantly more efficient".  In practical terms, a significant improvement might well be possible for relatively small graphs or graphs of special type.
