Rank-width and tree-width of \(H\)-minor-free graphs

DOI10.1016/j.ejc.2010.05.003zbMath1215.05171arXiv0910.0079OpenAlexW2073638763WikidataQ60488643 ScholiaQ60488643MaRDI QIDQ709231

Sang-il Oum, Dimitrios M. Thilikos, Fedor V. Fomin

Publication date: 18 October 2010

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph minors (05C83)

Related Items (16)

Subgraph densities in a surface ⋮ Tree densities in sparse graph classes ⋮ Number of Cliques in Graphs with a Forbidden Subdivision ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Cliques in graphs excluding a complete graph minor ⋮ On the number of cliques in graphs with a forbidden minor ⋮ Rank-width: algorithmic and structural results ⋮ Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ From tree-decompositions to clique-width terms ⋮ Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs ⋮ On the maximum number of cliques in a graph embedded in a surface ⋮ Comparing linear width parameters for directed graphs ⋮ Unnamed Item ⋮ Counting cliques in 1-planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• On forbidden subdivision characterizations of graph classes
• On the maximum number of cliques in a graph
• Colouring graphs with bounded generalized colouring number
• Intersection theorems with geometric consequences
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Graph minors. XI: Circuits on a surface
• Extremal set systems with restricted \(k\)-wise intersections.
• An improved linear edge bound for graph linkages
• Orderings on graphs and game coloring number
• The extremal function for complete minors
• Upper bounds to the clique width of graphs
• Graphs with linearly bounded Ramsey numbers
• Das Geschlecht des vollständigen paaren Graphen
• 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
• An extremal function for contractions of graphs
• Structural Properties of Sparse Graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• HYPERGRAPHS
• Radius two trees specify χ‐bounded classes
• Topological cliques in graphs II
• On the Relationship Between Clique-Width and Treewidth
• Der vollständige paare Graph auf nichtorientierbaren Flächen.
• Rank‐width is less than or equal to branch‐width

This page was built for publication: Rank-width and tree-width of \(H\)-minor-free graphs