# What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?

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.

## 1 Answer

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.

• So on high probability, we may assume that this kind of graph have chromatic number 2 I thing. That is $\chi(G(n,d/n)) = 2$ a.a.s? So the ultimate expected chromatic number does not have any effect of d? Jan 1, 2018 at 19:03
• No, you can't assume that. It is 3 with some nonzero probability and 2 with some nonzero probability. Jan 2, 2018 at 0:18