Shifts of the Stable Kneser Graphs and Hom-Idempotence

PABLO TORRES; MARIO VALENCIA-PABON

EUROPEAN JOURNAL OF COMBINATORICS

ACADEMIC PRESS LTD-ELSEVIER SCIENCE LTD

Lugar: Amsterdam; Año: 2017 vol. 62 p. 50 - 57

0195-6698

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 geq 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 $operatorname{KG}(n,k)$ are not weakly hom-idempotent for $n geq 2k+1$, $kgeq 2$. For $s geq 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 $operatorname{KG}(n,k)_{s-operatorname{stab}}$ and we show that $2$-stable Kneser graphs are not weakly hom-idempotent, for $n geq 2k+2$, $k geq 2$. Moreover, for $s,kgeq 2$, we prove that $s$-stable Kneser graphs $operatorname{KG}(ks+1,k)_{s-operatorname{stab}}$ are circulant graphs and so hom-idempotent graphs. Finally, for $s geq 3$, we show that $s$-stable Kneser graphs $operatorname{KG}(2s+2,2)_{s-operatorname{stab}}$ are cores, not $chi$-critical, not hom-idempotent and their chromatic number is equal to $s+2$.