Talk:Four color theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Former good article nominee Four color theorem was a Mathematics good articles nominee, but did not meet the good article criteria at the time. There are suggestions below for improving the article. Once these issues have been addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.
Article milestones
Date Process Result
April 7, 2009 Peer review Reviewed
October 29, 2009 Good article nominee Not listed
Current status: Former good article nominee
          This article is of interest to the following WikiProjects:
WikiProject Mathematics (Rated B-class, Top-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Top Priority
 Field: Topology
A selected article on the Mathematics Portal.
WikiProject Maps (Rated C-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Maps, a collaborative effort to improve the coverage of Maps and Cartography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
Checklist icon
 Top  This article has been rated as Top-importance on the project's importance scale.
WikiProject Geography (Rated B-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Geography, a collaborative effort to improve the coverage of geography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.

Four color theorem as applied to cell tower placement[edit]

Diagram showing circles (cell tower range) along a highway.

The four color theorem has been applied to cell tower placement; see here and search for "four color mapping theorem". Cell channel spectrums -- each one coming from a different tower -- can be thought of as colors, and only four are needed in flat places such as New Jersey.--Tomwsulcer (talk) 03:13, 19 April 2012 (UTC)

That does not look like a reliable source and its identification of planar maps with overlapping disks, solely because both types of things can be called two-dimensional, does not fill me with confidence in its mathematical rigor. —David Eppstein (talk) 03:42, 19 April 2012 (UTC)
It indicates to me that the four color theorem is of interest in the subject of cell tower placement. According to WP's rules about sources, the source is somewhat light since it is a blog; however, as you know, which sources we apply is a judgment call, and according to my personal judgment, it is a good source on this issue (I do not see any biases or reasons to discount it.) And blogs have been used elsewhere when appropriate. I did not make up the idea; it is not original research as was claimed when the addition of my diagram of cell tower placement was reverted. And I continue to believe that the issue of cell tower placement is a valid instance of one of the few real-world applications of the four color theorem.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)
It is easy to place five cell towers so that they all overlap each other. How does the four-color theorem apply in that case? What are the regions to be colored? —David Eppstein (talk) 15:13, 19 April 2012 (UTC)
My understanding (which may be imperfect here -- I am trying to follow the logic correctly -- please bear with me -- I am not an expert in anything unfortunately) is that each cell tower is like the center of a circle or sphere -- it broadcasts up to a fixed distance (the radius) so that a car or person with a cell phone within that radius can pick up the signal, and have a two-way conversation, essentially a walkie-talkie radio transmission between the cell phone and the tower (which, in turn, relays the conversation over the phone network or satellites or whatever it does). If a person/car using the cell phone moves to a different area, the cell phone system has to pick up the fact that the customer is moving, and hand off transmission duty to the second tower, that is, the cell phone company must cease transmitting from the first tower, and begin transmitting from the second tower. This handoff can not happen if both towers are using the same broadcast channels (if I understand this correctly -- I am kind of piecing together what the logic is -- I may be wrong about this) -- tower A has to broadcast on one channel, and tower B must use a different one. And, by analogy with the four color theorem, the broadcast channels are like colors -- each color is a different broadcast channel. So adjacent towers (circles, spheres) can not be the same color, or broadcast channel. For the cell phone company, it might be prohibitively expensive if it had to use up numerous different channels, that is, it can minimize costs and maximize profits by using the fewest number of different channels, that is, it is cheaper (and possibly simpler?) for it to use as few channels (or colors) as possible. And the four color theorem instructs cell tower placement people that they only need four channels to spread out their towers in a plane (I realize it's 3-D but for all practical purposes we can think of the problem as a plane). I came across this idea somewhere while working on the bio of a cell phone scientist, or maybe somewhere else (I do not remember exactly -- but I think there are at least two sources on this -- I can only find one now) and I can followup with him to ask him about this. The cell phone scientist is mathematically oriented like yourself and can perhaps enlighten me about whether this is a genuine application of the four color theorem, and if the assumptions are correct, so I will try to ask him when I see him next.--Tomwsulcer (talk) 15:59, 19 April 2012 (UTC)
My feeling is that if you're this vague on what the mathematical theory actually is, you shouldn't be trying to add it to a mathematics article here. —David Eppstein (talk) 16:28, 19 April 2012 (UTC)
Noted. My feeling is that it is a mistake to shut oneself off from differing viewpoints. None of us knows everything; knowledge (even math) is uncertain; please try to keep an open mind. I am not vague on the mathematical theory as it relates to this example but what is unclear to me are a few assumptions underlying how cell towers work as a system, and I will try to find this out. In deference to your expertise, I will heed your suggestion and keep the cell tower diagram out until I get more information. :) --Tomwsulcer (talk) 17:35, 19 April 2012 (UTC)
Update. I spoke with a cell tower scientist and mathematician who runs a division at Alcatel Lucent about the whole issue of applying the four color theorem to the task of intelligently placing cell towers along a highway. He knew about the four color theorem, and he said "it's possible". He said that some adjacent cell towers did indeed use different frequencies; that is, as a user in a car drives from the area of cell tower A, to the area of cell tower B, the handoff goes from one frequency to another frequency (as if they were different "colors"). But, he said there were instances in which the frequencies were the same on adjacent towers. So a person in between tower A and tower B might be talking via both towers simultaneously, and the cell phone company has some way to handle this using codes, somehow sorting out the timing and signals so that conversation was comprehensible. "It's complex" he said. Somehow, all this technology works. So I figure I will merely post this here, and let others decide whether to add anything to the four color theorem article; if I come upon new information, I will post it here too.--Tomwsulcer (talk) 12:13, 30 April 2012 (UTC)


More vivid colors.
There are points here where four shapes intersect.

I like the beautiful colors of the diagrams in this article but at the same time I see areas where improvements can be made:--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

United States diagram. I substituted the map of US states with a more vivid example; still, I think the US as an example of the four color theorem is problematic for three reasons: (1) Alaska & Hawaii are islands (2) four western states intersect in a single point, meaning we have to deal with this by either (a) explaining that New Mexico and Utah "don't touch" (I think they do btw) because they only share a single point or (b) use a different map or (c) find a way to use only four colors (I found a way). Still, I think using a different country, such as France (problem: Corsica) or Germany (better in my view) is a better alternative for us. In addition, many users here in WP complain there is an over-emphasis on things related to the United States.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

Top diagram. The first diagram, at the top of the page, while beautiful to look at, has four shapes intersecting in one point. I am dissatisfied with the explanation that the four shapes don't touch because they only touch only on one point -- in my view, the upper left and lower right areas are adjacent and touch, regardless of any attempted explanation at what adjacent means; and, as such, it does not constitute a good example of the four color theorem. It does not seem to be mathematically rigorous to have that diagram as an example of how the four color theorem is applied.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)


related to the same problem: you cannot connect 5 dots to each other on a 2d plane without crossing one of the lines, or placing the 5th point on a line, which invalidates the result.

extrapolating this info, it can be seen that in 1d space, 3 colors are needed (if only the sides of the lines count as adjacent, not the points). therefore in 3d space, 5 colors should be required to color a map.

furthermore, there is a simpler visual proof than a circle. it is best visualized as a triangle within a triangle, with one of the triangles being segmented into 3 areas. this is consistent with other 2d geometric theories. (talk) 00:33, 28 April 2012 (UTC)

In 3d space, many more than 5 colors may be required: there are maps (even having all regions be convex polyhedra) with arbitrarily large numbers of regions, all adjacent to each other. —David Eppstein (talk) 00:37, 28 April 2012 (UTC)
have any examples? interesting. actually, even thinking back to my own example, in 1d space the lines can only be ordered end-to-end, since making them adjacent would extend it to a 2nd dimension. curious about these 3d maps. (talk) 00:45, 28 April 2012 (UTC)
well, i can visualize it at least, seems 1d = 2 colors (most likely just 1 if vertices are not counted), 2d = 4 colors, 3d = infinity? still hard to wrap head around this, and would require proof if you have any ;p (talk) 00:53, 28 April 2012 (UTC)
An example. See in particular figure 1 of that paper. —David Eppstein (talk) 01:11, 28 April 2012 (UTC)
nice, thanks. it seems the 2 issues are related. ie: you can connect infinity objects using curved lines in 3d space to each other without crossing any other lines. if they are straight lines however, you can only connect 5 objects in 3d space. simple analogy here: if you have 10 objects, each with 9 pieces of string attached, connecting them to all other objects. however, in 2d space, even with splines, you cannot connect more than 4 objects without crossing any lines. same for straight lines in 2d. seems like what matters here is whether (or the amount of objects) than can be fully meshed. (coming from a networking background). ie: like a fully meshed/routed network. (talk) 03:31, 28 April 2012 (UTC)

Please read my article I write recently and give your precious opinion, Thank you a great deal! — Preceding unsigned comment added by Yuqiu54 (talkcontribs) 06:10, 4 July 2012 (UTC)

What was so wrong with Kempe's Chains[edit]

Kempe's chain method works on almost all planar graphs. Kempe's method failed to properly four color a very specific coloring of a specific graph. It seems that this is the only reason that Kempe was rejected. Are there any more compelling reasons for this decision?

Jillbones (talk) 06:27, 2 July 2013 (UTC)

Even one failure and it's not a proof. —David Eppstein (talk) 06:33, 2 July 2013 (UTC)

How about "failure with recovery"?

See for example

Further results can be found in the first 6 pages of my paper at arXiv :

Icahit (talk) 07:17, 9 September 2013 (UTC)

Arxiv is considered a self-published source, because there is little editorial control on the quality of its papers. To add it to this article, it would need to be published in a reputable mathematics journal. —David Eppstein (talk) 07:30, 9 September 2013 (UTC)


The Android game Untangle states this in its description:

For the more mathematically minded, the colors show that every graph is 3- or 4-colorable, which implies that it is planar and can be solved.

Is this implication true, or is it something that the game author made up? Essentially, if we consider the colourable regions as nodes of a planar graph, then this is claiming what can be considered a converse of the four-colour theorem: that every 4-colourable graph is planar.

But is this the case? It would be nice if we can find some information on the matter to add to the article. — Smjg (talk) 00:21, 25 July 2013 (UTC)

No it is not true, not even almost. Even being 2-colourable doesn't imply planarity, consider K3,3. McKay (talk) 04:41, 25 July 2013 (UTC)

Bad sentence[edit]

"However, the unavoidability part of the proof was verified in over 400 pages of microfiche, which had to be checked by hand (Appel & Haken 1989)." -- Microfiche is not a verification method but a storage medium. I don't have A&H handy so I can't check what they actually say, but this sentence needs editing to make it meaningful. McKay (talk) 04:47, 3 September 2013 (UTC)

Bad Troll. Learn 2 English. — Preceding unsigned comment added by (talk) 17:09, 27 December 2013 (UTC)

A minor thing[edit]

In the leading section: "Additionally, any map (regardless of whether it is a counterexample or not) must have a portion that looks like one of these 1,936 maps." Actually not "any map" but any map that satisfies some necessary conditions for being a minimal non-4-colourable triangulation (such as having minimum degree 5). The description later might have this problem too. McKay (talk) 03:25, 21 February 2014 (UTC)

OK, I changed the wording in the lead section to account for this. Opinions on whether this change is an improvement are always welcome. LouScheffer (talk) 12:59, 21 February 2014 (UTC)
OK, fixed the later wording too. Comments welcome. LouScheffer (talk) 13:05, 21 February 2014 (UTC)

Four colour maps... with five colours?[edit]

Am I the only one seeing five colours in the "four colour" geographic maps? Surely the ocean is also part of the map. The fact that we know from personal experience that that area isn't a country shouldn't matter. The maps can (should?) be rendered without using a 5th colour for the ocean(s). (talk) 03:10, 19 July 2014 (UTC)

n dimension[edit]

In n dimension, is there a "2n color theorem?"

For example, on a line, there is a 2 color theorem, in space, there is a 8 color theorem. — Preceding unsigned comment added by (talk) 16:41, 26 July 2014 (UTC)

No. It is possible to find a subdivision of three-dimensional space into convex regions all of which touch each other. For instance, take the Voronoi diagram of any discrete subset of points on the moment curve. —David Eppstein (talk) 18:20, 26 July 2014 (UTC)


The one true 4 color map ( is actually wrong, the Congo and Sudan are both yellow. I think this map is just wrong and not planned out properly. There's no way to fit in South Sudan, or to split up Czechoslovakia. KarstenO (talk) 16:13, 16 May 2015 (UTC)

I'm taking this map out of the article. As KarstenO points out, it shows two adjacent countries in Africa both in the same color, yellow. Loraof (talk) 19:31, 18 August 2015 (UTC)

World map examples[edit]

Although a world map can be colored with four colors, as the examples show, it is not the best example because it does not strictly satisfy the assumptions of the theorem, namely that a single region can't have disjoint segments like some countries do. But do we really have a better alternative?--Jasper Deng (talk) 20:44, 28 July 2015 (UTC)

A stronger conjecture[edit]

Is it true that if a graph (can be either planar or non-planar) does not contain a sub-graph homeomorphic to Kn (the complete graph on n vertices), then it can be painted with at most n-1 colors? For n=1, 2, 3, it is easy to prove, and Paul Dirac proved that it is true for n=4, but is it true for all natural number n? If the n=5 case is true, then it will imply the four color theorem, since a planar graph can't contain a sub-graph homeomorphic to K5. — Preceding unsigned comment added by (talkcontribs)

This is Hajós' stronger version of the Hadwiger conjecture. It is false: for n-vertex rndom graphs the biggest complete subdivision has a number of vertices proportional to the square root of n but the chromatic number is proportional to n/log n. See the Hadwiger conjecture article for details. —David Eppstein (talk) 17:24, 8 August 2015 (UTC)


(1) Given a map, is there a known algorithm to determine a valid coloring in polynomial time (or otherwise) in the number of regions? [It's mentioned in the section "simplification and verification".] Loraof (talk) 20:08, 18 August 2015 (UTC)

(2) Given a map, is there a known algorithm to determine in polynomial time (or otherwise) whether the map can be colored using just three colors or whether four are required?

If these are known, or are not known and are objects of research, it might be worthwhile to mention that in the article. Loraof (talk) 19:48, 18 August 2015 (UTC)

(2) is known to be NP-complete. It's mentioned at Graph coloring#Computational complexity but should probably also be included in this article. —David Eppstein (talk) 20:45, 18 August 2015 (UTC)