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.