论文标题
在广义旋塞图的树宽度上
On the treewidth of generalized Kneser graphs
论文作者
论文摘要
整数的广义旋转图$ k（n，k，t）$ $ k> t> 0 $和$ n> 2k-t $是其顶点为$ \ {1，\ dots，n \} $的$ k $ -subsets的图形，并且只有在相邻的两个角度相邻的情况下与$ t $ hsseals相邻。当$ t \ ge 2 $和$ n $与$ k $相比，我们确定广义旋转图$ k（n，k，t）$的树宽。对$ n $的施加限制是先前已知的界限的重大改进。我们结果的结果之一是以下内容。对于每个整数$ c \ ge 1 $，存在常数$ k（c）\ ge 2c $，以至于$ k \ ge k（c）$表示$ t = k-c $ t = k-c $ tw（k（n，k，k，t））= \ binom {n} （t+1）（k+1-t）$。
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,\dots,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\ge 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\ge 1$ there exists a constant $K(c)\ge 2c$ such that $k\ge K(c)$ implies for $t=k-c$ that $$tw(K(n,k,t))=\binom{n}{k}-\binom{n-t}{k-t}-1$$ if and only if $n\ge (t+1)(k+1-t)$ .
