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.
Recommendations
Cites work
- A new generalization of the Erdős-Ko-Rado theorem
- A new short proof for the Kruskal-Katona theorem
- A simple proof of the Erdős-Chao Ko-Rado theorem
- Almost cross-intersecting and almost cross-Sperner pairs of families of sets
- Almost Intersecting Families of Sets
- Generalized Kneser coloring theorems with combinatorial proofs
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 3489128 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1131873 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- Hypergraphs of Bounded Disjointness
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Kneser's conjecture, chromatic number, and homotopy
- S-functions for graphs
- The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
Cited in
(18)- On the treewidth of Hanoi graphs
- Sums of squares and quadratic persistence on real projective varieties
- Treewidth of the generalized Kneser graphs
- On the boxicity of Kneser graphs and complements of line graphs
- Erdös-Ko-Rado theorem for ladder graphs
- The treewidth of 2-section of hypergraphs
- Treewidth of the line graph of a complete graph
- On the book thickness of k-trees
- The \(q\)-analogue of zero forcing for certain families of graphs
- scientific article; zbMATH DE number 7731184 (Why is no real title available?)
- Treewidth of the \(q\)-Kneser graphs
- Kneser graphs are Hamiltonian
- On the treewidth of Hanoi graphs
- Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph
- On the treewidth of generalized q-Kneser graphs
- Kneser graphs are Hamiltonian
- Extremal G-free induced subgraphs of Kneser graphs
- On the expansion of Hanoi graphs
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)