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

  • $\begingroup$ 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? $\endgroup$ Jan 1, 2018 at 19:03
  • 1
    $\begingroup$ No, you can't assume that. It is 3 with some nonzero probability and 2 with some nonzero probability. $\endgroup$ Jan 2, 2018 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.