Talk:Four color theorem

Re: the recent added images of colorings of different countries

I agree with David Eppstein that adding an entire section as a gallery to simply present different countries with their colorings is a bit overkill (especially with the map of America's at the beginning). I was thinking, though, of re-adding at least one of them to the section "Use outside of mathematics," since it seems apt. I was originally just going to place the Germany one in, but maybe adding a picture of a real-life exclave forcing 5-colors would be nice. In any case, I don't think it hurts to add a second picture illustrating how it works, since non-math inclined people are probably going to be interested in (more than one) examples of these type. I didn't want to just make the edit immediately though since the similar one had just been reverted. What do other people think? _{Integral Python} ^{click here to argue with me} 21:58, 24 May 2023 (UTC)

Equivalence to torus coloring is wrong

The article says "Forcing two separate regions to have the same color can be modelled by adding a 'handle' joining them outside the plane. Such construction makes the problem equivalent to coloring a map on a torus (a surface of genus 1), which requires up to 7 colors for an arbitrary map." That seems to imply that there's a planar map with just one noncontiguous region that requires 7 colors. But you can 4-color the contiguous countries and then use 1 more color for the noncontiguous one, so you only need 5 colors. I don't know how this should be rewritten. Nylimb (talk) 14:41, 23 August 2023 (UTC)

I don't follow "4-color the contiguous countries and then use 1 more color for the noncontiguous one". The problem in this section is that both regions marked "A" are constrained to have the same color. Under that constraint, there should be a map which requires 7 colors (although we don't draw it using the "handle" style of visualization). There's probably a clearer way to say all this, for example expanding on the example in the section in "Generalizations" describing the torus coloring problem, but I'm not sure quite what this would look like and whether it would be an improvement. Kingdon (talk) 10:40, 14 July 2024 (UTC)

"Forcing two separate regions to have the same color can be modelled by adding a 'handle' joining them outside the plane" -- true.

"Such construction makes the problem equivalent to coloring a map on a torus" -- false, because a torus map can require seven colors, while five colors suffice for a planar map with a single two-region country.

Proof: Consider the map obtained by removing both of the "A" regions. That map is planar, so it can be four-colored. Apply that four-coloring to the original map, and use a fifth color for "A".

Should we just delete that paragraph? Joule36e5 (talk) 21:20, 14 July 2024 (UTC)

Another falsehood: "A similar construction also applies if a single color is used for multiple disjoint areas, as for bodies of water on real maps ... In such cases more colors might be required with a growing genus of a resulting surface.", because all the bodies of water can be given a single color, regardless of how much the genus would grow by adding handles connecting them all. Anyway, I would be fine with deleting from "Forcing two separate regions" to "(See the section Generalizations below.)". —David Eppstein (talk) 06:26, 15 July 2024 (UTC)

Cubic map

In the section on three-coloring, it is stated that "A cubic map can be colored with only three colors if and only if each interior region has an even number of neighboring regions." but I can't find any easily available explanation of what a cubic map is. Maybe this should be explained, rather than requiring people to pass a paywall to read the cited article before they can understand what that sentence means? MasterHigure (talk) 11:33, 4 January 2024 (UTC)

I've added a wikilink. Joule36e5 (talk) 00:23, 20 February 2024 (UTC)

Isn't this section just plain misleading? It states that "A cubic map can be colored with only three colors if and only if each interior region has an even number of neighboring regions." But then it gives the US map as an example of an application of this statement when the US map is in fact not cubic! Moreover, since planar graph 3-colorability is NP-complete, it cannot be that the simple cubic map criterion used for testing if three colors suffice can be applied in general to all planar maps (that are not cubic). --Litmus58 (talk) 18:40, 14 March 2024 (UTC)

Alternative non-mathematical explanation

Maybe a sentence added to the lead, to the effect of "It is impossible to draw five bodies that are all touching each other, which would be required for the theorem to be disproven", would help more practically-minded people to grasp it intuitively. :) --Kraligor (talk) 16:07, 19 February 2024 (UTC)

That would be incorrect. It is a very standard misunderstanding of the theorem. The actual theorem is not about the impossibility of five regions touching each other (for which see Kuratowski's theorem). Minimal graphs that require five colors do not have to have five vertices, just as minimal graphs that require three colors can be cycles of any odd length, not just triangles. —David Eppstein (talk) 18:15, 19 February 2024 (UTC)