From: Stefan Dantchev <dantchev@brics.dk>
Subject: Re: "fast" colouring of planar graphs
Date: Sun, 06 Jun 1999 15:01:30 +0200
Newsgroups: sci.math.research,sci.op-research

> Note that finding an optimal colouring (i.e. k=4) is known to be NP-hard.
> Is it known to be NP-hard for any *fixed* k>4 ?

	There is a proof of The Four Colour Theorem that gives a QUADRATIC
algorithm for finding a 4-colouring. A brief description is available at

	http://www.math.gatech.edu/~thomas/FC/fourcolor.html

Note that the value 4 might not be optimal. A planar graph can have a
chromatic
number less than 4. Checking whether it is 3 is NP-complete problem.