Rank-width and tree-width of H-minor-free graphs
From MaRDI portal
Publication:709231
DOI10.1016/J.EJC.2010.05.003zbMATH Open1215.05171DBLPjournals/ejc/FominOT10arXiv0910.0079OpenAlexW2073638763WikidataQ60488643 ScholiaQ60488643MaRDI QIDQ709231FDOQ709231
Sang-Il Oum, Fedor V. Fomin, Dimitrios M. Thilikos
Publication date: 18 October 2010
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0910.0079
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
- Intersection theorems with geometric consequences
- The extremal function for complete minors
- Upper bounds to the clique width of graphs
- 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
- Approximating clique-width and branch-width
- Graphs on surfaces
- Title not available (Why is that?)
- An extremal function for contractions of graphs
- Title not available (Why is that?)
- On the Relationship Between Clique-Width and Treewidth
- Lower bound of the Hadwiger number of graphs by their average degree
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- An improved linear edge bound for graph linkages
- Topological cliques in graphs II
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Rank‐width is less than or equal to branch‐width
- On the maximum number of cliques in a graph
- Radius two trees specify χ‐bounded classes
- On forbidden subdivision characterizations of graph classes
- HYPERGRAPHS
- Der vollständige paare Graph auf nichtorientierbaren Flächen.
- Structural Properties of Sparse Graphs
- Graphs with linearly bounded Ramsey numbers
- Colouring graphs with bounded generalized colouring number
- Orderings on graphs and game coloring number
- Graph minors. XI: Circuits on a surface
- Title not available (Why is that?)
- Das Geschlecht des vollständigen paaren Graphen
- Extremal set systems with restricted \(k\)-wise intersections.
Cited In (18)
- Counting cliques in 1-planar graphs
- Number of Cliques in Graphs with a Forbidden Subdivision
- A width parameter useful for chordal and co-comparability graphs
- Title not available (Why is that?)
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Approximate tree decompositions of planar graphs in linear time
- Tree densities in sparse graph classes
- Subgraph densities in a surface
- Comparing linear width parameters for directed graphs
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Cliques in graphs excluding a complete graph minor
- On the maximum number of cliques in a graph embedded in a surface
- Graphs of bounded depth‐2 rank‐brittleness
- From tree-decompositions to clique-width terms
- Rank-width: algorithmic and structural results
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- 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)
