Shifts of the Stable Kneser Graphs and Hom-Idempotence

preprint2016arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.