We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n$, $1. 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$. 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.
@article{10_37236_4673,
author = {Alan Frieze and Wesley Pegden},
title = {Between 2- and 3-colorability},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4673},
zbl = {1307.05203},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4673/}
}
TY - JOUR
AU - Alan Frieze
AU - Wesley Pegden
TI - Between 2- and 3-colorability
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4673/
DO - 10.37236/4673
ID - 10_37236_4673
ER -
%0 Journal Article
%A Alan Frieze
%A Wesley Pegden
%T Between 2- and 3-colorability
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4673/
%R 10.37236/4673
%F 10_37236_4673
Alan Frieze; Wesley Pegden. Between 2- and 3-colorability. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4673
