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)

Diagrams[edit]

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)

Relations[edit]

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. 64.250.81.218 (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. 64.250.81.218 (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 64.250.81.218 (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. 64.250.81.218 (talk) 03:31, 28 April 2012 (UTC)

Please read my article I write recently and give your precious opinion, Thank you a great deal! http://www.paper.edu.cn/index.php/default/releasepaper/content/201207-15 — 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 http://www.academia.edu/1179130/The_Four-Color_Map_Theorem_Kempes_Fallacious_Proof_Repaired_

Further results can be found in the first 6 pages of my paper at arXiv : http://arxiv.org/abs/0903.4108

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)

Converse?[edit]

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 205.221.255.62 (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). 85.138.248.47 (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 101.10.10.197 (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)

Congo[edit]

The one true 4 color map (http://upload.wikimedia.org/wikipedia/commons/a/a9/World_map_colored_using_the_four_color_theorem_including_oceans.png) 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 101.14.225.52 (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)

Algorithm?[edit]

(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)

Surely there are infinite maps that require four colours?[edit]

Hello,

Is this the right place to discuss an article? I am confused by the assertion that there are precisely 1,936 maps requiring four colours. As far as I can make out, there are three principal four colour maps, two of which can have a slight variation, and two of which can be modified to make an infinite number of maps. Thus there are infinite maps requiring four colours.

A friend of mine suggested that there were 1,936 *classes* of map. Is that correct? I cannot think of that many classes of map. What are they? Where can I see them?

Edmund

Exxxz (talk) 14:29, 23 December 2015 (UTC)

There were 1936 cases in the case analysis of the proof. There are as you say infinitely many planar graphs, most of which were not used as cases in this case analysis. —David Eppstein (talk) 17:17, 23 December 2015 (UTC)

Why is the number 1,936 significant?[edit]

I feel that the article needs editing. Any region surrounded by an odd number of other regions (apart from one) requires four colours, and any region divided into an odd number of sectors, surrounded by a one region ring requires four colours. Am I being obtuse, or is the number 1,936 actually significant? I make, as I wrote, that there are three principal four region maps, two of which can have a slight variation, and a different two of which (see above) can have more regions added, making two lots of infinite maps requiring four colours. Can someone please explicate what 1,936 maps have to do with anything?

Ed Z

Exxxz (talk) 16:15, 31 December 2015 (UTC)

Did you read the answer to almost the same question that you posted immediately above this one? —David Eppstein (talk) 19:13, 31 December 2015 (UTC)

Surely these are all the types of map?[edit]

What I am trying to work out, is what other principal four colour maps are there? These are all that I can think of...Exxxz (talk) 12:37, 5 January 2016 (UTC)

Exactly how many classes of maps requiring four colours are there?[edit]

As in my contribution including my .pdf, as above, are there more 'types' of map that I'm missing? If this is not the place to discuss the issue in general, then where should I go? Exxxz (talk) 14:35, 13 January 2016 (UTC)

In the proof of the theorem they have to test 1,476 reducible configurations. This indicates there are considerably more classes that the ones in our diagram. --Salix alba (talk): 22:20, 13 January 2016 (UTC)

Other principal four colour maps?[edit]

Hello Again, Hmm... Could someone actually post, or point me in the direction of the presumably vast number of classes of map that I am missing? Obviously one could add any number of random blobs to my maps, but I can't think of any more basic types of map other than those in my .pdf... Exxxz (talk) 18:31, 22 January 2016 (UTC)

Dude. This iis the sixth time you have opened a new section here to ask, essentally the same question. Have you even read any of the answers from the other five times you asked it? —David Eppstein (talk) 18:45, 22 January 2016 (UTC)
Exxxz, the four-color problem is not "find a map that requires four colors rather than three", but "show that no map requires FIVE colors". This is why your list of patterns isn't complete. For example, consider the map of a dodecahedron -- locally, it has pentagons surrounded by five other regions, as in one of your examples; but the fact that each such six-region neighborhood can be four-colored doesn't tell you whether that coloring can be extended to the rest of the map. (In fact, your first three patterns and their variations, besides being equivalent to each other, are not even among the 1936, as I understand it -- it's not hard to show that a minimal counterexample would have no regions with fewer than five neighbors.) Joule36e5 (talk) 02:34, 18 February 2016 (UTC)

Contradiction between two Wikipedia entries/sections/articles[edit]

The article "Francis Guthrie" states "At the time, Guthrie was a student of Augustus De Morgan at University College London" This is the second sentence, the first sentence referring to nobody else. Thus the Guthrie referred to is Francis Guthrie who is stated to be a student of De Morgan.

On the other hand the current article "Four Color theorem" states "At the time, Guthrie's brother, Frederick, was a student of Augustus De Morgan"

Both articles cannot be correct. — Preceding unsigned comment added by BrianAstle (talkcontribs) 16:16, 21 February 2016 (UTC)

I've edited Francis Guthrie to agree with this article, based upon this article. Paul August 15:09, 22 February 2016 (UTC)
I believe that is correct. McKay (talk) 05:35, 23 February 2016 (UTC)

Three color theorem[edit]

Is there's a possiblity of maps only having three colors? Has limitations? — Preceding unsigned comment added by 46.130.138.25 (talk) 18:19, 11 March 2016 (UTC)

If there are no points shared by only three regions (Grötzsch), or even if there are up to three such points (Grünbaum), then the map is 3-colorable. There are also some unproved conjectures about 3-colorability. I don't know if this is worth adding to this article, or perhaps some related article. (Grötzsch is already in the see-also section of this article.) Joule36e5 (talk) 01:59, 12 March 2016 (UTC)

Correct Formulation of Statement for Four-Color Problem[edit]

I am one of those who is not satisfied with a computer 'solving' the 4-Color Problem; however, my reason is simply that the 'proof' doesn't teach us anything. I've also tried to 'outwit' the 4 color constraint many times over many years, and something strikes me about the whole idea: namely that I can see why it's true; I just can't prove it. I've wondered for some time now if it would help to word (as well as think of) the problem in the following way:

    "On any effectively 2 dimensional surface such as a map or a globe, the greatest number of closed figures which can be drawn in such a way that each one touches every other one along a straight or curved side, is 4."

This makes the problem not so much about colors as about geometry and topology. The fourth shape always cuts off one or more of the others, so that additional shapes cannot touch one or more of the first 3. You can only escape this by veering into extra dimensions, or folding the paper (like hyperspace.) I may not be adequately describing this - and I certainly don't have the skills to prove it, but it is definitely a fundamental constraint, and that it what makes the 4-Color Theorem true.

Richard Deese 24.129.75.83 (talk) 09:46, 29 April 2016 (UTC)

That is a different and much easier problem, a form of Kuratowski's theorem. But it is easy to construct plane maps that require four colors despite not having four mutually-touching shapes, so the hard part of the four-color theorem is proving that this doesn't happen with one more color (requiring five colors despite not having five mutually-touching shapes). —David Eppstein (talk) 15:53, 29 April 2016 (UTC)