论文标题
广义旋格图的树宽
Treewidth of the generalized Kneser graphs
论文作者
论文摘要
令$ n $，$ k $和$ t $为整数，$ 1 \ leq t <k \ leq n $。 \ emph {generalized kneser graph} $ k（n，k，t）$是一个图形，其顶点是固定$ n $ set的$ k $ -subsets，其中两个$ k $ -subsets $ a $ a $ a $ a $ an and $ b $在$ | a \ cap b | <t $ <t $ ^ $ | <t $中。图$ k（n，k，1）$是众所周知的\ emph {kneser graph}。 2014年，哈维（Harvey）和伍德（Harvey and Wood）确定了相对于$ k $的大$ n $的kneser图的确切树宽。在本文中，我们以$ t \ geq2 $和大型$ n $相对于$ k $和$ t $给出了广义旋转图的确切树宽。在特殊情况下，当$ t = k-1 $时，图$ k（n，k，k-1）$通常由$ \ overline {j（n，k）} $表示，这是约翰逊图$ j（n，k）$的补充。对于任何$ n $和$ k $，我们给出了更精确的结果。
Let $n$, $k$ and $t$ be integers with $1\leq t< k \leq n$. The \emph{generalized Kneser graph} $K(n,k,t)$ is a graph whose vertices are the $k$-subsets of a fixed $n$-set, where two $k$-subsets $A$ and $B$ are adjacent if $|A\cap B|<t$. The graph $K(n,k,1)$ is the well-known \emph{Kneser graph}. In 2014, Harvey and Wood determined the exact treewidth of the Kneser graphs for large $n$ with respect to $k$. In this paper, we give the exact treewidth of the generalized Kneser graphs for $t\geq2$ and large $n$ with respect to $k$ and $t$. In the special case when $t=k-1$, the graph $K(n,k,k-1)$ usually denoted by $\overline{J(n,k)}$ which is the complement of the Johnson graph $J(n,k)$. We give a more precise result for the exact value of the treewidth of $\overline{J(n,k)}$ for any $n$ and $k$.
