Shifts of the stable Kneser graphs and hom-idempotence

Abstract

A graph G is said to be hom-idempotent if there is a homomorphism from G2 to G, and weakly hom-idempotent if for some n≥1 there is a homomorphism from Gn+1 to Gn. Larose et al. (1998) proved that Kneser graphs KG(n,k) are not weakly hom-idempotent for n≥2k+1, k≥2. For s≥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 KG(n,k)s−stab and we show that 2-stable Kneser graphs are not weakly hom-idempotent, for n≥2k+2, k≥2. Moreover, for s,k≥2, we prove that s-stable Kneser graphs KG(ks+1,k)s−stab are circulant graphs and so hom-idempotent graphs. Finally, for s≥3, we show that s-stable Kneser graphs KG(2s+2,2)s−stab are cores, not χ-critical, not hom-idempotent and their chromatic number is equal to s+2.