The grid theorem for vertex-minors

Abstract

We prove that, for each circle graph $H$, every graph with sufficiently large rank-width contains a vertex-minor isomorphic to $H$.

25 pages, 4 figures. Revised according to referees' comments. In press at JCTB

References in corpus (5)

• Rank-width: Algorithmic and structural results
• Finding branch-decompositions of matroids, hypergraphs, and more
• Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
• Scattered classes of graphs
• Vertex-minor-closed classes are $\chi$-bounded

Cited by in corpus (8)

• Obstructions for bounded shrub-depth and rank-depth
• Graphs of bounded cliquewidth are polynomially $\chi$-bounded
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• 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
• Intertwining connectivities for vertex-minors and pivot-minors
• Shallow vertex minors, stability, and dependence
• $t$-sails and sparse hereditary classes of unbounded tree-width