Rank-width and tree-width of H-minor-free graphs
From MaRDI portal
(Redirected from Publication:709231)
Abstract: We prove that for any fixed r>=2, the tree-width of graphs not containing K_r as a topological minor (resp. as a subgraph) is bounded by a linear (resp. polynomial) function of their rank-width. We also present refinements of our bounds for other graph classes such as K_r-minor free graphs and graphs of bounded genus.
Recommendations
- Rank-width and vertex-minors
- On rank-width of (diamond, even-hole)-free graphs
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. IV: Tree-width and well-quasi-ordering
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
- Tree-Related Widths of Graphs and Hypergraphs
- Graph minors. III. Planar tree-width
- On the tree-width of even-hole-free graphs
Cites work
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 3865318 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- An extremal function for contractions of graphs
- An improved linear edge bound for graph linkages
- Approximating clique-width and branch-width
- Colouring graphs with bounded generalized colouring number
- Das Geschlecht des vollständigen paaren Graphen
- Der vollständige paare Graph auf nichtorientierbaren Flächen.
- Extremal set systems with restricted \(k\)-wise intersections.
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Graph minors. XI: Circuits on a surface
- Graphs on surfaces
- Graphs with linearly bounded Ramsey numbers
- HYPERGRAPHS
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Intersection theorems with geometric consequences
- Lower bound of the Hadwiger number of graphs by their average degree
- On forbidden subdivision characterizations of graph classes
- On the Relationship Between Clique-Width and Treewidth
- On the maximum number of cliques in a graph
- Orderings on graphs and game coloring number
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Radius two trees specify χ‐bounded classes
- Rank‐width is less than or equal to branch‐width
- Structural Properties of Sparse Graphs
- The extremal function for complete minors
- Topological cliques in graphs II
- Upper bounds to the clique width of graphs
Cited in
(23)- Tree pivot-minors and linear rank-width
- Counting cliques in 1-planar graphs
- Approximate tree decompositions of planar graphs in linear time
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Approximate tree decompositions of planar graphs in linear time
- Comparing linear width parameters for directed graphs
- Tree densities in sparse graph classes
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Cliques in graphs excluding a complete graph minor
- Subgraph densities in a surface
- Scattered classes of graphs
- On the maximum number of cliques in a graph embedded in a surface
- Tree pivot-minors and linear rank-width
- Graphs of bounded depth‐2 rank‐brittleness
- From tree-decompositions to clique-width terms
- A formal proof of the minor-exclusion property for treewidth-two graphs
- The excluded tree minor theorem revisited
- Rank-width: algorithmic and structural results
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- Graphs of small rank-width are pivot-minors of graphs of small tree-width
- Number of cliques in graphs with a forbidden subdivision
- On the number of cliques in graphs with a forbidden minor
This page was built for publication: Rank-width and tree-width of \(H\)-minor-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q709231)
