Almost all graphs with $2.522 n$ edges are not 3-colorable

  • Dimitris Achlioptas
  • Michael Molloy

Abstract

We prove that for $c \geq 2.522$ a random graph with $n$ vertices and $m=cn$ edges is not 3-colorable with probability $1-o(1)$. Similar bounds for non-$k$-colorability are given for $k>3$.

Published
1999-07-01
Article Number
R29