Rank-width of random graphs

DOI10.1002/jgt.20620zbMath1244.05204arXiv1001.0461OpenAlexW3121193618MaRDI QIDQ2897211

Sang-il Oum, Choongbum Lee, Joonkyung Lee

Publication date: 10 July 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

sharp thresholdrandom graphclique-widthtree-widthrank-width

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items

Bounds for the Twin-Width of Graphs ⋮ Rank-width: algorithmic and structural results ⋮ A SAT Approach to Clique-Width ⋮ Nordhaus-Gaddum for treewidth ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ On the tree-depth of random graphs ⋮ Fractional Edge Cover Number of Model RB ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ On giant components and treewidth in the layers model ⋮ Large hypertree width for sparse random hypergraphs ⋮ On the tree-depth and tree-width in heterogeneous random graphs ⋮ On Treewidth and Related Parameters of Random Geometric Graphs

Cites Work

• Graph minors. III. Planar tree-width
• Treewidth. Computations and approximations
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• Expander graphs and their applications
• On the Threshold of Having a Linear Treewidth in Random Graphs
• Rank‐width is less than or equal to branch‐width

This page was built for publication: Rank-width of random graphs