From: kramsay@aol.com (KRamsay) Subject: Re: Geometry question Date: 08 May 1999 19:19:55 GMT Newsgroups: sci.math Keywords: chromatic number of non-planar graphs In article <37337DBC.1070FFFB@cs.berkeley.edu>, Jesus Cid-Sueiro writes: | This question states remembers me another one. Does the Four Colour |Theorem apply to any 2D surface, for instance, the surface of a Donut? It's not hard to convince yourself that every finite graph embeds in a surface having enough handles. Plainly the number of colors required grows without bound. Saaty and Kainen's book on the 4CT gives the number of colors required for every surface. They are the same as the maximum number of vertices in a complete graph that can be embedded in the surface (although this is far from obvious). A surface other than the Klein bottle requires [(7+sqrt(49-24e))/2] colors, where e is the Euler characteristic and [x] is the greatest integer <=x. The Klein bottle ------>>-------- | | | | | | ^ v | | | | | | ------>>-------- has Euler characteristic 0, but only 6 colors are required for it. The case of the plane 4CT was the LAST case to be proven. Keith Ramsay ============================================================================== From: hook@nas.nasa.gov (Edward C. Hook) Subject: Re: Geometry question Date: 8 May 1999 16:54:55 GMT Newsgroups: sci.math In article <37337DBC.1070FFFB@cs.berkeley.edu>, Jesus Cid-Sueiro writes: |> James Wanless wrote: |> > |> > Anybody know what the analogue to the Four Colour Theorem is in 3-D? |> > Thanks, |> > |> > -- |> > |> > James Wanless |> > www.jwanless.freeserve.co.uk |> |> This question states remembers me another one. Does the Four Colour |> Theorem apply to any 2D surface, for instance, the surface of a Donut? |> No, it concerns only maps drawn on the surface of the 2-dimensional sphere. For the other 2-manifolds, the corresponding result was discovered (and *proved*) much before Appel & Haken finished off the 4-Color Theorem: Theorem (due variously to Heawood, Young and/or Ringel for surfaces other than the 2-sphere): Let M be a connected 2-manifold with Euler characteristic e(M) and define the Heawood number of M, H(M), to be the greatest integer in { 7 + sqrt(49 - 24e(M)) }/2. Then, if M is _not_ the Klein bottle, any graph that embeds in M can be colored using no more than H(M) colors *and* there is at least one such graph that requires that many colors. If M is the Klein bottle, any graph in M can be colored with 6 colors (although H(Klein bottle) = 7). |> JCS -- Ed Hook | Copula eam, se non posit MRJ Technology Solutions, Inc. | acceptera jocularum. NAS, NASA Ames Research Center | I can barely speak for myself, much Internet: hook@nas.nasa.gov | less for my employer