Stability results for vertex Turan problems in Kneser graphs
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.
8130-PDF file-27887-2-10-20190429.pdf
publisher
openaccess
CC BY-ND
280.02 KB
Adobe PDF
c380dfdde5656e24806d2cc142e0856f