Between 2- and 3-colorability

Abstract

We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n,1<c\le 4$. We show that for any positive integer $\ell$, there exists $\epsilon =\epsilon (\ell )$ such that if $c=1+\epsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\ell +1}$ so long as its odd-girth is at least $2\ell +1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\chi (G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$.