joseph@hp-pcd.UUCP (joseph) (08/15/84)
--------------------------------------------------------------------------- That only 4 colors are needed for the 2-dimensional map has not been acceptably proved. A computer demonstration has been proposed, but the four color conjecture remains open. ----------------------------------------------------------------------------
eklhad@ihnet.UUCP (K. A. Dahlke) (08/15/84)
Hard about, we're entering clingon space !!! See, it's green. Here is a problem i solved this morning, you might be interested. When coloring the countries of a 2-dimensional map, at most 4 colors are needed. How many colors are necessary to color a 3-dimensional map. Imagine a blue federation glob, a green clingon glob, a red romulin glob, etc. The usual rules apply, sectors are adjacent if they have a surface in common. No two adjacent sectors should have the same color. In general, how many colors are needed for n dimensions? Answer in a week. enjoy. -- Karl Dahlke ihnp4!ihnet!eklhad
bradley@godot.UUCP (Bradley C. Kuszmaul) (08/17/84)
It takes lots and lots of colors...
Given N, I can construct N blobs which all touch each other in 3 space...
--Brad
--
{decvax!cca,ihnp4!mit-eddie,allegra!ias}!godot!bradley,
"godot!bradley@mit-eddie"@MIT-XX.ARPAgwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (08/20/84)
Sorry, the 4-color theorem HAS been proved (with computer assistance). I don't know anyone who is pleased with the proof, but it is generally accepted.
west@uiucdcs.UUCP (08/21/84)
#R:ihnet:-14900:uiucdcs:28200041:000:837 uiucdcs!west Aug 20 22:19:00 1984 The computer was used to aid in the search for a proof of the four color ``conjecture'', by selecting which cases to analyze. The resulting set of configurations has been checked by humans, and the proof is accepted by most graph theorists. What more do you want? The answer to the base note is correct, since it is easy to embed any 1-dimensional complex (i.e., graph) in 3-dimensional space. The appropriate generalization of the 4-color theorem is to surfaces of higher genus, not spaces of higher dimension. The resulting formula is Heawood's Theorem. For example, any graph drawn on the torus (i.e., doughnut) can be colored with 7 colors, and this is best possible. Curiously, for the higher genus the upper bound was the easy part, while showing that some graph with that chromatic number embeds on that surface took 80 years.