Stability results for vertex Turatn 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.


Published in:
Electronic Journal Of Combinatorics, 26, 2, P2.13
Year:
May 03 2019
Publisher:
Newark, ELECTRONIC JOURNAL OF COMBINATORICS
ISSN:
1077-8926
Laboratories:




 Record created 2019-06-18, last modified 2019-07-08


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)