From: Gerhard Woeginger <gwoegi@figipc56.tu-graz.ac.at>
Subject: Re: 3-color map theorem
Date: 21 Feb 2001 11:23:57 GMT
Newsgroups: sci.math
Summary: Brooks' theorem: (almost) any cubic graph is 3-colorable

Jan Kristian Haugland <jkhaug00@studnospam.hia.no> 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 ?
> >
> > >No (contradiction)
> >
> > >          -----
> > >         /  |  \
> > >        / A | B \
> > >       /   /^\   \
> > >      /   / C \   \
> > >     /___/_____\___\
> > >     |      D      |
> > >     |             |
> > >     ---------------
> >
> > >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.

Yes, that is the theorem of Brooks. It says that any cubic
graph is 3-colorable, unless one of its connected components
is the K_4.  Planarity is not required.

-Gerhard

>  Jan Kristian Haugland
>  http://home.hia.no/~jkhaug00