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ős-Ko-Rado Theorem (for large $n$ with respect to $k$) when a number of disjoint pairs of $k$-sets are allowed.
@article{10_37236_3971,
author = {Daniel J. Harvey and David R. Wood},
title = {Treewidth of the {Kneser} graph and the {Erd\H{o}s-Ko-Rado} theorem},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3971},
zbl = {1300.05084},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3971/}
}
TY - JOUR
AU - Daniel J. Harvey
AU - David R. Wood
TI - Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3971/
DO - 10.37236/3971
ID - 10_37236_3971
ER -
%0 Journal Article
%A Daniel J. Harvey
%A David R. Wood
%T Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3971/
%R 10.37236/3971
%F 10_37236_3971
Daniel J. Harvey; David R. Wood. Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3971
