On the 3-Colourability Threshold

                 Paul Dunne and Michele Zito

        Department of Computer Science, Liverpool University


Experimental studies  indicate that  a number of  NP-complete decision
problems  P exhibit  the following  behaviour: if  X_n is  the  set of
instances of  size n and  m is some  parameter of instances x  in X_n,
then instances for which m is small are almost all such that x is in P
and instances for which  m is large almost all are such  that x is not
in P.  Furthermore there is an  apparent threshold m* such that m < m*
implies that almost all  x belong to P and m >  m* implies that almost
all x do not belong to P.   We obtain upper bounds on the threshold in
3-colouring  n-vertex  graphs.    An  elementary  first-moment  method
suiffices to show that almost  all graphs with average degree at least
5.419 are not 3-colourable.  An improved analysis brings this constant
down to 5.277.  The technique generalizes to k-colouring.