rh@mit-eddie.UUCP (Randy Haskins) (02/16/84)
I had thought that 4 color planar had been proved, but that the "conjectures" of 5 colors for a sphere and 7 for a torus were still waiting. (Those numbers are right, aren't they?) -- Randwulf (Randy Haskins); Path= genrad!mit-eddie!rh
holmes@dalcs.UUCP (Ray Holmes) (02/17/84)
[] The four colour problem is the same for a sphere as it is for the infinite plane. The problem for a torus was solved many years ago. The torus needs exactly 7 colours to paint it. Ray
mcmillan@eosp1.UUCP (John McMillan) (02/17/84)
It was proved long ago that 7 colors suffices for a Torus. I believe that a sphere cannot require more colors than a plane. The proofof this (?) is as follows: You can convert a sphere into a plane by piercing a hole in it the size of a point, and then stretching it out flat. In a colored map, no countries meet at a point; they must share a border that has some length. Therfore piercing a hole in a spherical map does not change any of its boundary conditions, while converting it into a plane. - Toby Robison allegra!eosp1!robison decvax!ittvax!eosp1!robison princeton!eosp1!robison (NOTE! NOT McMillan; Robison.)
ags@pucc-i (Seaman) (02/18/84)
> I had thought that 4 color planar had been proved, but that > the "conjectures" of 5 colors for a sphere and 7 for a torus > were still waiting. (Those numbers are right, aren't they?) The sphere problem is equivalent to a plane problem. Just prick a whole in the middle of one of the regions and flatten it into a plane. Therefore 4 colors are sufficient for a sphere. Seven colors were known to be necessary and sufficient on a torus, long before the four-color proof was found for the planar case. -- Dave Seaman ..!pur-ee!pucc-i:ags "Against people who give vent to their loquacity by extraneous bombastic circumlocution."
davy@ecn-ee.UUCP (02/18/84)
#R:mit-eddi:-129000:ecn-ee:15300004:000:401 ecn-ee!davy Feb 17 09:21:00 1984 I'm sorry if this is a stupid question, but just what is the "four color problem"? For that metter, what's all this about a taurus (or is it torus?)? Since most everyone else probably knows this, please respond by mail and I'll post one summary if there's interest. Thanks, --Dave Curry decvax!pur-ee!davy (best for UUCP) inuxc!pur-ee!davy eevax.davy@purdue (best for ARPA) pur-ee!davy@Berkeley
segre@uicsl.UUCP (02/18/84)
#R:mit-eddi:-129000:uicsl:15500029:000:1585 uicsl!segre Feb 17 10:05:00 1984 Not quite...perhaps this will help clear things up: The Heawood Theorem (1890) gives an upper limit on the chromatic number for graphs embeddable on surfaces of genus > 0 as follows: chi(G) .LE. floor([7 + sqrt(1 + 48 gamma) ] / 2) where chi(G) is the chromatic number of a graph G and gamma is the genus of the surface. Note that surface refers to an orientable surface (i.e. having two sides: rules out things like the Mobius strip). The genus of a sphere is 0, that of a torus is 1. Note that planar graphs are those embeddable on the sphere. Although Heawood's theorem gives an upper bound, it doesn't tell us that this is the best possible bound: to do so, we must first see that the (minimum) genus (i.e. the surface of smallest genus on which the given graph G is embeddable) of the complete graph on n vertices (call it K-sub-n) is given by: gamma(K-sub-n) = ceiling( [(n-3)(n-4)] / 12) Proof of this is quite complex, involving 12 cases (one to show each congruence class of K-sub-n is embeddable on a surface of this genus). Therefore, we see that for surfaces of genus > 0 Heawood's theorem gives the best bound on chromatic number. Thus the "colorability" of higher order surfaces such as the torus and double-torus has been well understood since 1890. Note that if you plug in 0 for gamma in Heawood's theorem you get 4, implying that graphs embeddable on the sphere (plane) are 4-colorable. However, Heawood's proof explicitly calls for non-zero gamma -- which is why the 4 Color Theorem was still only conjecture after 1890. Alberto Segre uiucdcs!uicsl!segre
davy@ecn-ee.UUCP (02/23/84)
#R:mit-eddi:-129000:ecn-ee:15300005:000:1121 ecn-ee!davy Feb 22 08:38:00 1984 Thanks to all who responded about my question of "what is the four color problem". For those of you who also don't know, a brief explanation (from sdcrdcf!darrelj) is: A long time conjecture in mathematics was that any planar map of regions (e.g. the United States minus anomalies like a two-piece Michigan) could be colored in such a way that every pair of regions which share a border are different color using no more than 4 distinct colors (also, sharing a single finite number of points only do NOT share a border). It was believed true for the last 100 years (and many erroneous proofs were offerred), until a few years ago, mathemeticians at U. of Illinois generated a proof, the short part of which said "all graphs without properties xxx can be four-colored, the long part of which was a computer generation of all the thousands of graphs with the messy properties combined with an enumeration of how to color each one. There are related kinds of problems for other topological surfaces such as the surface of a sphere and the surface of a torus (doughnut). --Dave Curry