Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
复制标题
DOI：
10.37236/3971
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Daniel J. Harvey;D. Wood
中科院分区：
文献类型：
--
作者：
Daniel J. Harvey;D. Wood
树宽是一个重要的和众所周知的图参数，衡量一个图的复杂性。Kneser图Kneser$（n，k）$是顶点集为$\binom{[n]}{k}$的图，如果两个顶点不相交，则它们相邻。我们确定，对于大值的$n$关于$k$，确切的树宽的Kneser图。在这样做的过程中，我们还证明了加强的Erdens-Ko-Rado定理（对于大$n$关于$k$）时，允许一些不相交的对$k$-集。
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.