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