Treewidth of the \(q\)-Kneser graphs

DOI10.1016/j.dam.2023.09.004arXiv2101.04518MaRDI QIDQ6184322

Ke Liu, Zequn Lv, Mengyu Cao, Mei Lu

Publication date: 24 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treewidthtree decompositionGrassmann graph\(q\)-Kneser graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
• The eigenvalues of \(q\)-Kneser graphs
• On the chromatic number of \(q\)-Kneser graphs
• The treewidth of line graphs
• Kneser's conjecture, chromatic number, and homotopy
• Graph minors. III. Planar tree-width
• Graph minors. I. Excluding a forest
• Erdős-Ko-Rado theorem, Grassmann graphs and \(p^s\)-Kneser graphs for vector spaces over a residue class ring
• A characterization of Grassmann and Johnson graphs
• Treewidth of the generalized Kneser graphs
• The energy of \(q\)-Kneser graphs and attenuated \(q\)-Kneser graphs
• The Erdős-Ko-Rado theorem for twisted Grassmann graphs
• Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On the treewidth of random geometric graphs and percolated grids
• On Treewidth and Related Parameters of Random Geometric Graphs
• Treewidth of Cartesian Products of Highly Connected Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth