Shifts of the Stable Kneser Graphs and Hom-Idempotence

Abstract

A graph $G$ is said to be {\em hom-idempotent} if there is a homomorphism from $G^2$ to $G$, and {\em weakly hom-idempotent} if for some $n\ge 1$ there is a homomorphism from $G^{n+1}$ to $G^n$. Larose et al. [{\em Eur. J. Comb. 19:867-881, 1998}] proved that Kneser graphs $\mathrm{KG}(n,k)$ are not weakly hom-idempotent for $n\ge 2k+1$, $k\ge 2$. For $s\ge 2$, we characterize all the shifts (i.e., automorphisms of the graph that map every vertex to one of its neighbors) of $s$-stable Kneser graphs $\mathrm{KG}(n,k{)}_{s-\mathrm{stab}}$ and we show that $2$-stable Kneser graphs are not weakly hom-idempotent, for $n\ge 2k+2$, $k\ge 2$. Moreover, for $s,k\ge 2$, we prove that $s$-stable Kneser graphs $\mathrm{KG}(ks+1,k{)}_{s-\mathrm{stab}}$ are circulant graphs and so hom-idempotent graphs. Finally, for $s\ge 3$, we show that $s$-stable Kneser graphs $\mathrm{KG}(2s+2,2{)}_{s-\mathrm{stab}}$ are cores, not $\chi$-critical, not hom-idempotent and their chromatic number is equal to $s+2$.