Vertex-minors of graphs: a survey

DOI10.1016/J.DAM.2024.03.011MaRDI QIDQ6495258FDOQ6495258

Authors: Donggyu Kim, Sang-Il Oum 

Publication date: 30 April 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• The complexity of the vertex-minor problem
• scientific article; zbMATH DE number 4202305
• Vertex-minor reductions can simulate edge contractions
• Recognizing locally equivalent graphs
• scientific article; zbMATH DE number 808801

zbMATH Keywords

prime graphlocal complementationrank-widthvertex-minorcircle graphinterlace polynomial

Mathematics Subject Classification ID

Graph minors (05C83) Discrete mathematics in relation to computer science (68Rxx) Designs and configurations (05Bxx)

Cites Work

• Title not available (Why is that?)
• Decomposition of regular matroids
• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• Unavoidable vertex-minors in large prime graphs
• Graph minors. XIII: The disjoint paths problem
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• The relative clique-width of a graph
• Graphs on surfaces
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph minors. V. Excluding a planar graph
• Distance-hereditary graphs
• Circle graph obstructions
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Tree-depth and vertex-minors
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Linear time split decomposition revisited
• Decomposition of Directed Graphs
• Planar Graphs
• Rank‐width is less than or equal to branch‐width
• Graphic presentations of isotropic systems
• Reducing prime graphs and recognizing circle graphs
• Local complementation and interlacement graphs
• Title not available (Why is that?)
• Greedy algorithm and symmetric matroids
• Recognizing circle graphs in polynomial time
• Isotropic matroids. II: Circle graphs
• Ramsey-type theorems
• Graph minors XXIII. Nash-Williams' immersion conjecture
• The branchwidth of graphs and their cycle matroids
• Graph minors. XVI: Excluding a non-planar graph
• Solving Rota's conjecture
• On the chromatic number of multiple interval graphs and overlap graphs
• On Rota's conjecture and excluded minors containing large projective geometries.
• Menger's theorem for matroids
• Isotropic systems
• Tutte-Martin polynomials and orienting vectors of isotropic systems
• Interlace polynomials
• On the interlace polynomials
• Graph polynomials derived from Tutte-Martin polynomials
• Title not available (Why is that?)
• The interlace polynomial of a graph
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Transforming trees by successive local complementations
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
• Rank-Width and Well-Quasi-Ordering
• Unimodularity and circle graphs
• Obstructions for linear rank-width at most 1
• Linear rank-width and linear clique-width of trees
• Excluding a bipartite circle graph from line graphs
• Circle graph obstructions under pivoting
• Graph-Theoretic Concepts in Computer Science
• Thread graphs, linear rank-width and their algorithmic applications
• Title not available (Why is that?)
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Graph-Theoretic Concepts in Computer Science
• An efficient algorithm to recognize locally equivalent graphs
• Title not available (Why is that?)
• On the connectivity function of a matroid
• Title not available (Why is that?)
• Tree pivot-minors and linear rank-width
• Title not available (Why is that?)
• Rank-width: algorithmic and structural results
• Minimally 3-connected isotropic systems
• Title not available (Why is that?)
• Computing small pivot-minors
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Vertex-minors and the Erdős-Hajnal conjecture
• Obstructions for bounded shrub-depth and rank-depth
• Branch-depth: generalizing tree-depth of graphs
• Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
• The complexity of the vertex-minor problem
• Twin-width. I: Tractable FO model checking
• The grid theorem for vertex-minors
• Graphs of bounded cliquewidth are polynomially \(\chi\)-bounded
• Rank connectivity and pivot-minors of graphs
• Title not available (Why is that?)
• Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
• Circle graphs are quadratically χ‐bounded
• The interlace polynomial and the Tutte–Martin polynomial
• Improved bounds for colouring circle graphs
• Counting single-qubit Clifford equivalent graph states is \#\(\mathbb{P}\)-complete
• Intertwining Connectivities for Vertex-Minors and Pivot-Minors
• Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded
• Prime vertex-minors of a prime graph

This page was built for publication: Vertex-minors of graphs: a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6495258)