  We prove that in sparse Erd\H{o}s-R\'{e}nyi graphs of average degree $d$, the
vector chromatic number (the relaxation of chromatic number coming from the
Lov\`{a}sz theta function) is typically $\tfrac{1}{2}\sqrt{d} + o_d(1)$. This
fits with a long-standing conjecture that various refutation and
hypothesis-testing problems concerning $k$-colorings of sparse
Erd\H{o}s-R\'{e}nyi graphs become computationally intractable below the
`Kesten-Stigum threshold' $d_{KS,k} = (k-1)^2$. Along the way, we use the
celebrated Ihara-Bass identity and a carefully constructed non-backtracking
random walk to prove two deterministic results of independent interest: a lower
bound on the vector chromatic number (and thus the chromatic number) using the
spectrum of the non-backtracking walk matrix, and an upper bound dependent only
on the girth and universal cover. Our upper bound may be equivalently viewed as
a generalization of the Alon-Boppana theorem to irregular graphs
