Treewidth of the generalized Kneser graphs (Q2121803): Difference between revisions

Summary: Let \(n\), \(k\) and \(t\) be integers with \(1\leqslant t< k \leqslant n\). The 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 Kneser graph. \textit{D. J. Harvey} and \textit{D. R. Wood} [Electron. J. Comb. 21, No. 1, Research Paper P1.48, 11 p. (2014; Zbl 1300.05084)] 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\geqslant 2\) and large \(n\) with respect to \(k\) and \(t\). In the special case when \(t=k-1\), the graph \(K(n, k, k-1)\) is 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\).