Parameters Tied to Treewidth
From MaRDI portal
Publication:2978180
DOI10.1002/jgt.22030zbMath1359.05030arXiv1312.3401OpenAlexW2345501529MaRDI QIDQ2978180
Daniel J. Harvey, David R. Wood
Publication date: 21 April 2017
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.3401
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)
Related Items (30)
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Tree densities in sparse graph classes ⋮ An improved planar graph product structure theorem ⋮ Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ Separating layered treewidth and row treewidth ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Graphs of linear growth have bounded treewidth ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ On Ramsey Size-Linear Graphs and Related Questions ⋮ The product structure of squaregraphs ⋮ Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree ⋮ Induced subgraphs and path decompositions ⋮ Graph product structure for non-minor-closed classes ⋮ On strict brambles ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ The treewidth of line graphs ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Directed Path-Decompositions ⋮ Better bounds for poset dimension and boxicity ⋮ Notes on graph product structure theory ⋮ Treewidth of graphs with balanced separations ⋮ The Size Ramsey Number of Graphs with Bounded Treewidth ⋮ On the tree-depth and tree-width in heterogeneous random graphs ⋮ The treewidth of 2-section of hypergraphs ⋮ Characterizing Tseitin-formulas with short regular resolution refutations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Clique minors in Cartesian products of graphs
- Constant-degree graph expansions that preserve treewidth
- Polynomial treewidth forces a large grid-like-minor
- Some recent progress and applications in graph minor theory
- Achievable sets, brambles, and sparse treewidth obstructions
- Treewidth lower bounds with brambles
- Nonrepetitive colorings of graphs of bounded tree-width
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- S-functions for graphs
- A partial k-arboretum of graphs with bounded treewidth
- Highly connected sets and the excluded grid theorem
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Graph searching and a min-max theorem for tree-width
- Quickly excluding a planar graph
- Multiplicities of eigenvalues and tree-width of graphs
- Fractional colouring and Hadwiger's conjecture
- On simple characterizations of k-trees
- Coloring with no 2-colored \(P_4\)'s
- Graph minors. XIII: The disjoint paths problem
- Tree-width and planar minors
- Incidence matrices and interval graphs
- On tree width, bramble size, and expansion
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Graph minors. IV: Tree-width and well-quasi-ordering
- On the Parameterized Intractability of Monadic Second-Order Logic
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A Separator Theorem for Planar Graphs
- h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area
- Layout of Graphs with Bounded Tree-Width
This page was built for publication: Parameters Tied to Treewidth
