2016/04/24 by Torres, Pablo, Valencia-Pabon, Mario
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1604.07023
A graph G is said to be \em hom-idempotent if there is a homomorphism from G2 to G, and \em weakly hom-idempotent if for some n ≥ 1 there is a homomorphism from Gn+1 to Gn. Larose et al. [\em Eur. J. Comb. 19:867-881, 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.