How many "different" colorings (excluding exchanges) exist for a given map (graph)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:54:20Z http://mathoverflow.net/feeds/question/61225 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph How many "different" colorings (excluding exchanges) exist for a given map (graph)? Mario Stefanutti 2011-04-10T17:07:22Z 2012-12-22T05:24:06Z <p>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 analyzine) 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.</p> <p><a href="http://4coloring.files.wordpress.com/2011/04/3-colored-in-12-different-ways.png" rel="nofollow">http://4coloring.files.wordpress.com/2011/04/3-colored-in-12-different-ways.png</a></p> <p>My question is: how many "different" colorings (in the meaning I explained) exist for a given map? I've only found an article on <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow">http://en.wikipedia.org/wiki/Graph_coloring</a> that count all possible colorings including swaps. Is there a paper that can help me on this?</p> <p>I already posted it to "math stackexchange" but, so far, I haven't received the answer I was looking for.</p> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/61233#61233 Answer by Siva for How many "different" colorings (excluding exchanges) exist for a given map (graph)? Siva 2011-04-10T18:10:56Z 2011-04-10T18:10:56Z <p>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. <a href="http://en.wikipedia.org/wiki/Chromatic_polynomial" rel="nofollow">http://en.wikipedia.org/wiki/Chromatic_polynomial</a></p> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/61285#61285 Answer by Christian Blatter for How many "different" colorings (excluding exchanges) exist for a given map (graph)? Christian Blatter 2011-04-11T11:16:41Z 2011-04-11T11:16:41Z <p>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:</p> <p><a href="http://retro.seals.ch/digbib/view?rid=ensmat-001:1965:11::337&amp;id=browse&amp;id2=browse5&amp;id3=1" rel="nofollow">http://retro.seals.ch/digbib/view?rid=ensmat-001:1965:11::337&amp;id=browse&amp;id2=browse5&amp;id3=1</a></p> <p>In this paper the permutations of colors are systematically "quotiented out" via a certain homological process.</p> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/68735#68735 Answer by Matt Brin for How many "different" colorings (excluding exchanges) exist for a given map (graph)? Matt Brin 2011-06-24T13:47:19Z 2011-06-24T13:47:19Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>Note that the assumption that regions intersect in connected sets is a large assumption. Without that assumption, the number of colorings would explode.</p> <p>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.</p> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/68737#68737 Answer by Emil Jeřábek for How many "different" colorings (excluding exchanges) exist for a given map (graph)? Emil Jeřábek 2011-06-24T14:03:56Z 2011-06-24T14:03:56Z <p>Counting the number of 4-colorings (or indeed, \$k\$-colorings for any fixed \$k\ge3\$) of a planar graph is a <a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow"><code>\$\#P\$</code>-complete</a> problem (as proved by <a href="http://dx.doi.org/10.1137/S0097539704446797" rel="nofollow">Vertigan</a>), hence it (presumably) cannot be computed by any algorithm significantly more efficient than a brute-force search.</p> http://mathoverflow.net/questions/61225/how-many-different-colorings-excluding-exchanges-exist-for-a-given-map-graph/117008#117008 Answer by Thomas Zaslavsky for How many "different" colorings (excluding exchanges) exist for a given map (graph)? Thomas Zaslavsky 2012-12-22T05:24:06Z 2012-12-22T05:24:06Z <p>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.</p> <p>I disagree with Emil Jer&aacute;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.</p>