Unavoidable vertex-minors in large prime graphs
From MaRDI portal
Abstract: A graph is prime (with respect to the split decomposition) if its vertex set does not admit a partition (A,B) (called a split) with |A|, |B| >= 2 such that the set of edges joining A and B induces a complete bipartite graph. We prove that for each n, there exists N such that every prime graph on at least N vertices contains a vertex-minor isomorphic to either a cycle of length n or a graph consisting of two disjoint cliques of size n joined by a matching.
Recommendations
- Unavoidable minors of graphs of large type
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- On unavoidable-induced subgraphs in large prime graphs
- scientific article; zbMATH DE number 1303530
- Minors in graphs of large girth
- On minimal prime graphs and posets
- Unavoidable minors of large 3-connected matroids
- On unavoidable graphs
- Unavoidable minors of large 3-connected binary matroids
- Graphs with unavoidable subgraphs with large degrees
Cites work
- Approximating clique-width and branch-width
- Circle graph obstructions
- Circle graph obstructions under pivoting
- Decomposition of Directed Graphs
- Graph theory
- Graph-Theoretic Concepts in Computer Science
- Graphic presentations of isotropic systems
- scientific article; zbMATH DE number 15493 (Why is no real title available?)
- Isotropic systems
- Rank-width and vertex-minors
- Recognizing circle graphs in polynomial time
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- Typical subgraphs of 3- and 4-connected graphs
- Unavoidable doubly connected large graphs
- Unavoidable minors of large 3-connected binary matroids
- Unavoidable parallel minors of 4-connected graphs
Cited in
(14)- Obstructions for bounded shrub-depth and rank-depth
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- Prime orientable graphs
- Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
- Unavoidable induced subgraphs in large graphs with no homogeneous sets
- scientific article; zbMATH DE number 1156646 (Why is no real title available?)
- On unavoidable-induced subgraphs in large prime graphs
- Scattered classes of graphs
- Unavoidable subtournaments in large tournaments with no homogeneous sets
- Determination of the prime bound of a graph
- Graphs of bounded depth‐2 rank‐brittleness
- Prime vertex-minors of a prime graph
- Vertex-minors of graphs: a survey
- An overview of universal obstructions for graph parameters
This page was built for publication: Unavoidable vertex-minors in large prime graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q740266)
