Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set $\binom{ [n]}{ k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erd\H{ o}s-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pairs of k-sets are allowed.

Categories: math.CO

Treewidth of the Kneser Graph and the Erd\H{o}s-Ko-Rado Theorem