Rank-width of random graphs

DOI10.1002/jgt.20620zbMath1244.05204arXiv1001.0461MaRDI 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 threshold; random graph; clique-width; tree-width; rank-width

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

Related Items

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

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