In 1978 Lovasz introduced the neighborhood complex of a graph and used topology to give lower bounds on the chromatic number of graphs. His bound was tight for Kneser graphs, and it is natural to ask what kinds of graphs are most likely to be amenable to topological bounds on chromatic number. In this talk I'll discuss two different kinds of random graphs -- the Erdos-Renyi model, and Borsuk like random graphs on the sphere. For the first kind of graph, Lovasz's topological bounds are very far from the chromatic number. For the second kind, they are tight. In this talk, I will sketch proofs of these facts, highlightling the necessary topological ideas. The talk will aim to be self-contained - no prerequisite knowledge about the subject will be assumed.