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

Daniel Harvey, David Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

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 ([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 Erdo{double acute}s-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pairs of k-sets are allowed.

Original languageEnglish
Article numberP1.48
Pages (from-to)1 - 11
Number of pages11
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number1
Publication statusPublished - 28 Feb 2014

Keywords

  • Erdo{double acute}s-Ko-Rado
  • Graph theory
  • Kneser graph
  • Separators
  • Treewidth

Cite this