Files

Abstract

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Alishahi and Taherkhani, whenever n is large enough compared to k and F. In this paper, we determine the second largest size of a vertex set W subset of V such that K(n, k)[W] is F-free, in the case when F is an even cycle or a complete multi-partite graph. In the latter case, we actually give a more general theorem depending on the chromatic number of F.

Details

Actions

Preview