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.