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$.


Full Text: PDF