On random subgraphs of Kneser and Schrijver graphs

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic number of a Kneser graph KG,k is equal to n 2k +2. In this paper we study the chromatic number of a random subgraph of a Kneser graph KG,,,k as n grows. A random sub graph KG, k(p) is obtained by including each edge of KO.,k with probability p. For a wide range of parameters k = k(n), p = p(n) we show that x(KG,,,,k (p)) is very close to x(KGn,k), w.h.p. differing by at most 4 in many cases. Moreover, we obtain the same bounds on the chromatic numbers for the so-called Schrijver graphs, which are known to be vertex -critical induced subgraphs of Kneser graphs. (C) 2016 Published by Elsevier Inc.