Between 2- and 3-colorability (Q5919171)

Summary: We consider the question of the existence of homomorphisms between \(G_{n,p}\) and odd cycles when \(p=c/n\), \(1<c\leq 4\). We show that for any positive integer \(\ell\), there exists \(\varepsilon=\varepsilon(\ell)\) such that if \(c=1+\varepsilon\) 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\). These results imply the existence of random graphs with circular chromatic numbers \(\chi_c\) satisfying \(2<\chi_c(G)<2+\delta\) for arbitrarily small \(\delta\), and also that \(2.5\leq \chi_c(G_{n,\frac 4 n})<3\) w.h.p..