A Note on the Non-Colorability Threshold of a Random Graph
A Note on the Non-Colorability Threshold of a Random Graph
In this paper we consider the problem of establishing a value $r_0$ such that almost all random graphs with $n$ vertices and $rn$ edges, $r > r_0$, are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy …