Rank-width and vertex-minors
From MaRDI portal
Publication:2565688
DOI10.1016/j.jctb.2005.03.003zbMath1070.05023OpenAlexW2170114629MaRDI QIDQ2565688
Publication date: 28 September 2005
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2005.03.003
Related Items (only showing first 100 items - show all)
Circle graph isomorphism in almost linear time ⋮ A chain theorem for sequentially 3-rank-connected graphs with respect to vertex-minors ⋮ Twin-distance-hereditary digraphs ⋮ Critical properties of bipartite permutation graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Prime vertex-minors of a prime graph ⋮ Unnamed Item ⋮ Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Intertwining Connectivities for Vertex-Minors and Pivot-Minors ⋮ Tree-depth and vertex-minors ⋮ Rainbow independent sets on dense graph classes ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ Betweenness in Order-Theoretic Trees ⋮ Between treewidth and clique-width ⋮ On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ The relative clique-width of a graph ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The rank-width of edge-coloured graphs ⋮ Transforming graph states using single-qubit operations ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Rank-width: algorithmic and structural results ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Grammars and clique-width bounds from split decompositions ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ A polynomial kernel for block graph deletion ⋮ Unnamed Item ⋮ Subgraph complementation ⋮ Infinitely many minimal classes of graphs of unbounded clique-width ⋮ Regularity Equals Monadic Second-Order Definability for Quasi-trees ⋮ Local 2-separators ⋮ Classification of real Bott manifolds and acyclic digraphs ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Bichain graphs: geometric model and universal graphs ⋮ Graph reductions, binary rank, and pivots in gene assembly ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Counting single-qubit Clifford equivalent graph states is #P-complete ⋮ Boundary Classes of Planar Graphs ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ 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 ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Unnamed Item ⋮ The nullity theorem for principal pivot transform ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ Obstructions for linear rank-width at most 1 ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Matroids that classify forests ⋮ The group structure of pivot and loop complementation on graphs and set systems ⋮ Branch decomposition heuristics for linear matroids ⋮ Clique-width with an inactive label ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ The average cut-rank of graphs ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Circle graphs and monadic second-order logic ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Several notions of rank-width for countable graphs ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ A Menger-like property of tree-cut width ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Block-graph width ⋮ Recent developments on graphs of bounded clique-width ⋮ On the approximate compressibility of connected vertex cover ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Pivots, determinants, and perfect matchings of graphs ⋮ Chi-boundedness of graph classes excluding wheel vertex-minors ⋮ Excluding a bipartite circle graph from line graphs ⋮ Isotropic matroids. I: Multimatroids and neighborhoods ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Computing with Tangles ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Scattered Classes of Graphs ⋮ Vertex-minors and the Erdős-Hajnal conjecture ⋮ Unavoidable vertex-minors in large prime graphs ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Circle graph obstructions under pivoting ⋮ The complexity of the vertex-minor problem ⋮ On an extension of distance hereditary graphs ⋮ Circle graphs and the cycle double cover conjecture ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Characterizing matroids whose bases form graphic delta-matroids ⋮ Graph operations characterizing rank-width ⋮ Efficient parallel algorithms for parameterized problems ⋮ Comparing linear width parameters for directed graphs ⋮ Digraphs of Bounded Width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The interlace polynomial of a graph
- A decomposition theory for matroids. I: General results
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Graph minors. V. Excluding a planar graph
- Distance-hereditary graphs
- Isotropic systems
- Graph minors. X: Obstructions to tree-decomposition
- Circle graph obstructions
- Quickly excluding a planar graph
- On the excluded minors for the matroids of branch-width \(k\)
- Branch-width and well-quasi-ordering in matroids and graphs.
- Upper bounds to the clique width of graphs
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Approximating clique-width and branch-width
- Graph minors. IV: Tree-width and well-quasi-ordering
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Transforming trees by successive local complementations
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Menger's theorem for matroids
- Graph-Theoretic Concepts in Computer Science
- Matrices and matroids for systems analysis
This page was built for publication: Rank-width and vertex-minors
