Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions

DOI10.1016/j.ejc.2018.07.009zbMath1394.05024arXiv1508.04718OpenAlexW2964029049WikidataQ129383519 ScholiaQ129383519MaRDI QIDQ1671752

Mamadou Moustapha Kanté, O-joung Kwon

Publication date: 7 September 2018

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

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

zbMATH Keywords

distance-hereditary graphslinear rank-widthrank-widthmatroid branch-widthmatroid path-widthvertex-minors

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Paths and cycles (05C38) Combinatorial aspects of matroids and geometric lattices (05B35) Graph minors (05C83) Distance in graphs (05C12)

Related Items (6)

\(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ 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 ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Scattered Classes of Graphs ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Outerplanar obstructions for matroid pathwidth
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• Graph minors. XX: Wagner's conjecture
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Completely separable graphs
• Graph minors. I. Excluding a forest
• Distance-hereditary graphs
• Isotropic systems
• Graphic presentations of isotropic systems
• Reducing prime graphs and recognizing circle graphs
• Complement reducible graphs
• Quickly excluding a forest
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• The vertex separation and search number of a graph
• Linear rank-width and linear clique-width of trees
• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
• Obstructions for linear rank-width at most 1
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Graph minors. IV: Tree-width and well-quasi-ordering
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• On the Monadic Second-Order Transduction Hierarchy
• Excluding a bipartite circle graph from line graphs
• Matroid Pathwidth and Code Trellis Complexity
• Rank-Width and Well-Quasi-Ordering
• Transforming trees by successive local complementations
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Graph Minors I: A Short Proof of the Path-width Theorem

This page was built for publication: Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions