From: gwoegi@opt.math.tu-graz.ac.at (Gerhard J. Woeginger) Subject: Re: outerplanar => 3-colorable Date: Mon, 29 Jan 2001 17:39:53 Newsgroups: sci.math.research Summary: 3-colorability of restricted families of graphs In article Todd Wilson writes: >Subject: outerplanar => 3-colorable >From: Todd Wilson >Date: 28 Jan 2001 18:42:40 -0800 >By the Four Color Theorem, every outerplanar graph is three-colorable. >Does anyone have a citation for a direct proof of this result? > >Todd Wilson This is folklore and quite easy to prove: Since every outerplanar graph has a vertex with degree at most 2, an inductive proof works. Chvatal (A combinatorial theorem in plane geometry, JCT Series B 18, 1975, 39-41) uses three colorability of outerplanar graphs for getting a bound for the art gallery problem. ___________________________________________________________ Gerhard J. Woeginger (gwoegi@opt.math.tu-graz.ac.at) ============================================================================== From: David Eppstein Subject: Re: outerplanar => 3-colorable Date: Mon, 29 Jan 2001 08:39:09 -0800 Newsgroups: sci.math.research In article , Todd Wilson wrote: > By the Four Color Theorem, every outerplanar graph is three-colorable. > Does anyone have a citation for a direct proof of this result? Just remove degree-two vertices one at a time. You can show there exists a degree-two vertex from the fact that the weak dual of an outerplanar graph, i.e. planar dual with the vertex corresponding to the infinite face deleted, is a forest, so it always has at least one leaf. Alternatively, you can use Euler's formula. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: Fred W. Helenius Subject: Re: 3-color map theorem Date: Wed, 21 Feb 2001 10:18:34 -0500 Newsgroups: sci.math Jan Kristian Haugland wrote: >Leroy Quet wrote: >> Jan Willem Knopper wrote: >> >>Is it true that: >> >>If you have a flat map, where every country is of a convex shape >> >>without any holes, then one can always color the map with just 3 >> >>colors such that no two boardering countries are colored the same ? [snip diagram] >> >Since all countries are adjacent, no pair can have the same colour. >> >> Ah, yes. >> What if all of the countries are triangles ? >Isn't there a theorem saying that the chromatic >number of any cubic planar graph except for the >tetrahedron is at most 3? That would answer the >question. I don't see how. Why should the graph be cubic -- can't a triangle have more than three triangular neighbors? And you would need to rule out the tetrahedron... Regardless, the answer to Leroy's question is no; four triangular regions can be mutually adjacent: ______________________ \\_ __==/ \ \_ __== / \ \_ __== / / \ \= / / \ \_ / / \ \_/ / \ / / \ / / \ / / \ // \/ -- Fred W. Helenius