6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Let me see if I understand you correctly: you are looking at maps that are 4-colorable, but not 3-colorable. So given any coloring, you can simply move the colors around in exactly 4! ways (since you have to use all 4 colors) and get essentially the same coloring. So isn't the number you're looking for simply the number of colorings divided by 4! ? $\endgroup$
    – Thierry Zell
    Commented Apr 10, 2011 at 18:11
  • $\begingroup$ @all: Thanks for the info. Yes, it is the problem I'm facing. But to get the "number of colorings" the only method I found is to compute the chromatic polynomial, which is known only for few graphs and it is hard to find for more complex cases. Do you know of papers that directly approach the computation of the "number of colorings without exchanges of colors"? I've implemented a brute force algorithm to color a given map with four colors. I'll try to extend it to find all possible colorings manually ... excluding exchanges. youtube.com/user/mariostefanutti#p/u/2/YmYGFxtj2es $\endgroup$
    – Mario Stefanutti
    Commented Apr 12, 2011 at 15:02

5 Answers 5

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Printed. I'm not that expert but I'll try to read it. Thanks! $\endgroup$
    – Mario Stefanutti
    Commented Apr 12, 2011 at 15:07
  • 1
    $\begingroup$ @jeq: The link has be repaired and should work now. $\endgroup$
    – Christian Blatter
    Commented Nov 29, 2017 at 19:05
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hi, how did you make these computations? I was planning to implement this feature into the program I'm building, but I'm having trouble to eliminate maps that "seems" different but that are actually the same map (Homeomorphic maps). See this other post: mathoverflow.net/questions/62328/… $\endgroup$
    – Mario Stefanutti
    Commented Jun 28, 2011 at 14:48
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer. I inserted a note to comment made by "Thierry Zell". It applies also to this comment. Thanks again. $\endgroup$
    – Mario Stefanutti
    Commented Apr 12, 2011 at 15:06
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ By “significantly more efficient”, I meant computable in time $2^{n^{o(1)}}$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 22, 2012 at 15:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .