What is the chromatic number of the ER graph $G(n,d/n)$, when $d < 1$ (there exist expressions for $d > 1$, but what if the graph is super sparse?). Here $n$ is the number of vertices and $d/n$ is the edge generation probability. 



What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?
Consider subgraphs consisting of two cycles with an edge in common (i.e. a theta-graph or something more complex). The number of such labelled graphs with $t$ vertices is at most $n^t$, and the probability of each is at most $(d/n)^{t+1}$ since they have at least $t+1$ edges. Summing over $t$ shows that the expected number of such subgraphs goes to 0 for $d\le 1$, implying that the probability of any such graphs appearing also goes to 0. So a random graph in this range has only cycles that can be coloured independently, plus tree-like stuff. The chromatic number is 3 if any cycle is odd (which has constant probability $c(d)$ I think) and 2 or less otherwise.


ADDED: The expected number of odd cycles is asymptotically
$$E(d) = \sum\_{i=1}^\infty \frac {d^{2i+1}}{4i+2} = -\frac d2 + \frac14\ln\frac{1+d}{1-d}.$$
Since the distribution of the number of odd cycles is asymptotically Poisson, the probability that there are no odd cycles is asymptotically
$$P(d) = \exp(-E(d)) = e^{d/2}\biggl( \frac{1-d}{1+d}\biggr)^{1/4}.$$
Since the probability of having no edges at all is infinitesimal, asymptotically the probability that $\chi(G)=2$ is $P(d)$ and the probability that $\chi(G)=3$ is $1-P(d)$. I suggest you plot these functions for $0\le d\le 1$ to see what they look like.


