From: Stefan Dantchev
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.