Stable Kneser graphs: problems and conjectures

For positive integers n \ge 2k, the Kneser graph KG(n, k) has as vertices the k-subsets of [n] = {1,…,n} and two vertices are connected by an edge if they have empty intersection. In particular, for s \ge 2, the s-stable Kneser graph is the subgraph of KG(n, k) induced by the k-subsets S of [n] such that the circular distance between any two elements in S is at least s. For this graph class there are several open problems, among them the hom-idempotence and finding its chromatic number. Some papers solve these problems in particular instances, but the general case remains open. In this talk we show some conjectures and advances on them.

SLIDES from the talk are here.