Excluded vertex-minors for graphs of linear rank-width at most \(k\)

DOI10.1016/j.ejc.2014.04.010zbMath1297.05228arXiv1311.2618OpenAlexW2294116080MaRDI QIDQ740279

Jisu Jeong, Sang-il Oum, O-joung Kwon

Publication date: 2 September 2014

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

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

zbMATH Keywords

block graphgraph width parameter

Mathematics Subject Classification ID

Graph minors (05C83) Distance in graphs (05C12)

Related Items (12)

Rank-width: algorithmic and structural results ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\) ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Several notions of rank-width for countable graphs ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Scattered Classes of Graphs ⋮ The complexity of the vertex-minor problem ⋮ Linear rank-width and linear clique-width of trees

Cites Work

• Unnamed Item
• Forbidden graphs for tree-depth
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Distance-hereditary graphs
• Graphic presentations of isotropic systems
• Upper bounds on the size of obstructions and intertwines
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• On the excluded minors for the matroids of branch-width \(k\)
• Algorithms and obstructions for linear-width and related search parameters
• Obstructions for linear rank-width at most 1
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Excluded vertex-minors for graphs of linear rank-width at most k.
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• Rank-Width and Well-Quasi-Ordering
• Transforming trees by successive local complementations
• Decomposition of Directed Graphs

This page was built for publication: Excluded vertex-minors for graphs of linear rank-width at most \(k\)