2022/03/26 by Klaus Metsch, Metsch, Klaus
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2203.14036
The generalized Kneser graph K(n,k,t) for integers k>t>0 and n>2k-t is the graph whose vertices are the k-subsets of \1,…,n\ with two vertices adjacent if and only if they share less than t elements. We determine the treewidth of the generalized Kneser graphs K(n,k,t) when t≥ 2 and n is sufficiently large compared to k. The imposed bound on n is a significant improvement of a previously known bound. One consequence of our result is the following. For each integer c≥ 1 there exists a constant K(c)≥ 2c such that k≥ K(c) implies for t=k-c that tw(K(n,k,t))=\binomnk-\binomn-tk-t-1 if and only if n≥ (t+1)(k+1-t) .