Treewidth of the $q$-Kneser graphs

Abstract

Let $V$ be an $n$-dimensional vector space over a finite field ${\mathbb{F}}_q$, where $q$ is a prime power. Define the \emph{generalized $q$-Kneser graph} $K_q(n,k,t)$ to be the graph whose vertices are the $k$-dimensional subspaces of $V$ and two vertices $F_1$ and $F_2$ are adjacent if $\dim (F_1\cap F_2)<t$. Then $K_q(n,k,1)$ is the well-known $q$-Kneser graph. In this paper, we determine the treewidth of $K_q(n,k,t)$ for $n\ge 2t(k-t+1)+k+1$ and $t\ge 1$ exactly. Note that $K_q(n,k,k-1)$ is the complement of the Grassmann graph $G_q(n,k)$. We give a more precise result for the treewidth of $\overline{G_q(n,k)}$ for any possible $n$, $k$ and $q$.

10 pages