# Colorize and the Four-Color Theorem

We can write:

MorphologicalComponents[image] // Colorize


To assign a random set of colors to each component in some image. The example used for reference by Mathematica is a map of the United States: http://reference.wolfram.com/mathematica/ref/Colorize.html?q=Colorize&lang=en

My question is - is it possible to ask Mathematica to specify that any two adjacent colors should have some minimum threshold distance in in their hue or RGB values (e.g. http://en.wikipedia.org/wiki/File:Map_of_United_States_vivid_colors_shown.png)? I believe asking for a four-coloring of a map is computationally non-trivial, but are there any built-in routines, perhaps with the graph analytics packages in Mathematica, to allow for this?

Let's define two morphological components as adjacent if the line segments spanning the shortest distance between the two components fails to intersect any other morphological components. We can also include a distance $D$ cutoff for defining two components as adjacent. I'm certainly open to stricter definitions.

• Related Stan Wagon's article library.wolfram.com/infocenter/Articles/1157 Jul 10, 2013 at 18:32
• Can you elaborate more, what you exactly mean when you say adjacent color? Remember, that morphological components color objects which are not connected to each other. Jul 10, 2013 at 20:01
• @halirutan I've updated to question to offer a definition. Please let me know if you find issue with it. Jul 10, 2013 at 20:08
• If you figure out how to build the adjacency graph, then you can use one of the several colouring functions from IGraph/M. Minimum colouring is also supported so you can get a 4-colouring that way. May 1, 2018 at 13:15

I believe asking for a four-coloring of a map is computationally non-trivial,

In theory, yes. [[Well, I should add that I think it has not been proven to be of non-polynomial time.]] But in practice, getting a 4-coloring can be done quickly. My book, Mathematica in Action has chapter 17 devoted to this topic. Kempe's 1879 method works fine almost always. If it does get stuck, as Heawood in 1892 pointed out is possible, one can just start over with a permutation of the graph. We have found this idea (only sketchily discussed here) works very well and has no problem 4-coloring the graph made from all 3300+ counties in the USA.

The code in Chapter 17 includes code to 4-color planar graphs and, slightly more complicated, planar maps (such as the Martin Gardner hoax from April Fools Day, 1975).

• Very nice... +1 Jul 11, 2013 at 9:27
• Stan, would you care to post some minimal example? Jul 11, 2013 at 9:53
• Note sure how to post art on this site. Here is a PDF with some diagrams illustrating my points. Jul 12, 2013 at 13:47

I'm not entirely sure, but I believe in general this is not possible, because you can construct situations where you cannot guarantee that you have enough colors with a certain distance from each other.

One very simply construction is the following

img = Binarize@
Rasterize[
PolarPlot[2 {Sin[20 t], Cos[20 t]}^2 + 2, {t, 0, 2 Pi},
PlotPoints -> 100, MaxRecursion -> 5, Axes -> False,
PlotStyle -> AbsoluteThickness[2]], "Image",
ColorSpace -> "Grayscale"];
MorphologicalComponents[img] // Colorize


In this construction you have the color in the middle of the circle needs virtually an unlimited amount of color which have the required minimum distance in color space. Additionally, you have to outside blue-greenish color which needs the same property and finally, every color on the circle as 2 neighbors for which you need to ensure the distance.

Taking this as starting point, you can easily think of more complicated constructs having far more neighboring colors. Since the rgb-cube (or whatever color-space representation you choose) is a finite volume, I believe in general you cannot always create a coloring with the required property.

• Doesn't the four-color theorem guarantee us a solution where every border can be between two (simply connected and contiguous) countries of different colors? I'm not requiring that every border for a country requires a distinct pair of colors. Jul 10, 2013 at 20:55
• A four-coloration of your example might be to color to two big components in the center and outside contour RED and BLUE respectively, and then to alternatively color the small ellipsoids YELLOW and GREEN going around the circle. That would satisfy my definition of "adjacent" where a "border" implies that a line can be drawn between two components without intersecting any other components. Jul 10, 2013 at 21:04
• @SnowTrace Would you mind joining the chat? Maybe we can discuss this better there. Jul 10, 2013 at 21:05
• Hmm... I need a bit more reputation for that. If you can wait a bit, I'll join in later. Jul 10, 2013 at 21:09
• @SnowTrace Try now. Jul 10, 2013 at 21:10