Circular Coloring and Mycielski Construction

Abstract

In this paper, we investigate circular chromatic number of Mycielski construction of graphs. It was shown in \cite{MR2279672} that $t^{\mathrm{th}}$ Mycielskian of the Kneser graph $KG(m,n)$ has the same circular chromatic number and chromatic number provided that $m+t$ is an even integer. We prove that if $m$ is large enough, then $\chi (M^t(KG(m,n)))={\chi }_c(M^t(KG(m,n)))$ where $M^t$ is $t^{\mathrm{th}}$ Mycielskian. Also, we consider the generalized Kneser graph $KG(m,n,s)$ and show that there exists a threshold $m(n,s,t)$ such that $\chi (M^t(KG(m,n,s)))={\chi }_c(M^t(KG(m,n,s)))$ for $m\ge m(n,s,t)$.