Obstructions for linear rank-width at most 1
From MaRDI portal
Publication:2442201
DOI10.1016/j.dam.2013.05.001zbMath1285.05043arXiv1106.2533OpenAlexW1977080760WikidataQ59899339 ScholiaQ59899339MaRDI QIDQ2442201
Andrzej Proskurowski, Isolde Adler, Arthur M. Farley
Publication date: 2 April 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1106.2533
Related Items
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 ⋮ 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 ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Clique-width with an inactive label ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Linear rank-width and linear clique-width of trees ⋮ Tree Pivot-Minors and Linear Rank-Width
Cites Work
- Unnamed Item
- Graph minors. I. Excluding a forest
- Distance-hereditary graphs
- A partial k-arboretum of graphs with bounded treewidth
- Circle graph obstructions
- Obstruction set isolation for the gate matrix layout problem
- Edge dominating set and colorings on graphs with fixed clique-width
- 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
- Rank-width and vertex-minors
- Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
- Rank-Width and Well-Quasi-Ordering
- Better Polynomial Algorithms on Graphs of Bounded Rank-Width
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Graph Minors I: A Short Proof of the Path-width Theorem