Let $n$, $k$ and $t$ be integers with $1\leq t< k \leq 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|. The graph $K(n,k,1)$ is the well-known 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$.
@article{10_37236_10035,
author = {Ke Liu and Mengyu Cao and Mei Lu},
title = {Treewidth of the generalized {Kneser} graphs},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10035},
zbl = {1486.05260},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10035/}
}
TY - JOUR
AU - Ke Liu
AU - Mengyu Cao
AU - Mei Lu
TI - Treewidth of the generalized Kneser graphs
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10035/
DO - 10.37236/10035
ID - 10_37236_10035
ER -
%0 Journal Article
%A Ke Liu
%A Mengyu Cao
%A Mei Lu
%T Treewidth of the generalized Kneser graphs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10035/
%R 10.37236/10035
%F 10_37236_10035
Ke Liu; Mengyu Cao; Mei Lu. Treewidth of the generalized Kneser graphs. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10035
