Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem

From MaRDI portal



Abstract: Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set , such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the ErdH{o}s-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pairs of k-sets are allowed.


Summary: Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser\((n,k)\) is the graph with vertex set \(\binom{[n]}{k}\), such that two vertices are adjacent if they are disjoint. We determine, for large values of \(n\) with respect to \(k\), the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado theorem (for large \(n\) with respect to \(k\)) when a number of disjoint pairs of \(k\)-sets are allowed.











This page was built for publication: Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405143)