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

zbMath1300.05084arXiv1310.5400MaRDI QIDQ405143

Daniel J. Harvey, David R. Wood

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.5400

zbMATH Keywords

treewidth; Kneser graph; separators; Erdős-Ko-Rado

Mathematics Subject Classification ID

05D05: Extremal set theory

05C75: Structural characterization of families of graphs

05C12: Distance in graphs

Related Items

Unnamed Item, Treewidth of the \(q\)-Kneser graphs, Extremal \(G\)-free induced subgraphs of Kneser graphs, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• A new short proof for the Kruskal-Katona theorem
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• Graph minors XXIII. Nash-Williams' immersion conjecture
• S-functions for graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• Almost cross-intersecting and almost cross-Sperner pairs of families of sets
• A simple proof of the Erdős-Chao Ko-Rado theorem
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Graph minors. II. Algorithmic aspects of tree-width
• Almost Intersecting Families of Sets
• Hypergraphs of Bounded Disjointness
• A new generalization of the Erdős-Ko-Rado theorem