The grid theorem for vertex-minors

DOI10.1016/j.jctb.2020.08.004zbMath1504.05271arXiv1909.08113OpenAlexW2973492097MaRDI QIDQ2099410

Rose McCarty, Jim Geelen, O-joung Kwon, Paul Wollan

Publication date: 23 November 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

clique-widthrank-widthvertex-minors

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Intertwining Connectivities for Vertex-Minors and Pivot-Minors ⋮ Improved bounds for colouring circle graphs ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Scattered Classes of Graphs ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Isotropic matroids. II: Circle graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Graph minors. V. Excluding a planar graph
• Graphic presentations of isotropic systems
• Unavoidable minors of large 3-connected binary matroids
• Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Rank-width: algorithmic and structural results
• Infinitely many minimal classes of graphs of unbounded clique-width
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Excluding a bipartite circle graph from line graphs
• Scattered Classes of Graphs
• Finding branch-decompositions of matroids, hypergraphs, and more
• Graphs of bounded cliquewidth are polynomially $χ$-bounded

This page was built for publication: The grid theorem for vertex-minors