Unavoidable induced subgraphs in large graphs with no homogeneous sets

DOI10.1016/J.JCTB.2016.01.008MaRDI QIDQ256979zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Ringi Kim, Sang-Il Oum, Paul Seymour

Publication date 14 March 2016

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

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

zbMATH Keywords

induced subgraphmodular decompositionprime graphRamsey theory

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A homogeneous set of an $n$-vertex graph is a set $X$ of vertices ($2le|X|len-1$) such that every vertex not in $X$ is either complete or anticomplete to $X$. A graph is called prime if it has no homogeneous set. A chain of length $t$ is a sequence of $t+1$ vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all $n$, there exists $N$ such that every prime graph with at least $N$ vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from $K_{1,n}$ by subdividing every edge once, (2) the line graph of $K_{2,n}$, (3) the line graph of the graph in (1), (4) the half-graph of height $n$, (5) a prime graph induced by a chain of length $n$, (6) two particular graphs obtained from the half-graph of height $n$ by making one side a clique and adding one vertex.

Recommendations

• Unavoidable Induced Subgraphs of Large 2-Connected Graphs
• On unavoidable-induced subgraphs in large prime graphs
• Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
• Graphs with unavoidable subgraphs with large degrees
• On graphs induced by non-empty subsets
• scientific article; zbMATH DE number 15664
• scientific article; zbMATH DE number 125483
• On graphs with subgraphs having large independence numbers
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• The poset of unlabeled induced subgraphs of a finite graph

Cites work

• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• Extension of hereditary classes with substitutions
• Graph theory
• Graphs indecomposable with respect to the X-join
• Normal hypergraphs and the perfect graph conjecture
• Typical subgraphs of 3- and 4-connected graphs
• Unavoidable doubly connected large graphs
• Unavoidable vertex-minors in large prime graphs

Cited in

(10)

• Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
• scientific article; zbMATH DE number 125483 (Why is no real title available?)
• A Ramsey-type theorem for the matching number regarding connected graphs
• Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
• Well-quasi-ordering and Embeddability of Relational Structures
• Jónsson posets
• Unavoidable subtournaments in large tournaments with no homogeneous sets
• Resolutions of convex geometries
• On unavoidable-induced subgraphs in large prime graphs
• A finiteness theorem for primal extensions

This page was built for publication: Unavoidable induced subgraphs in large graphs with no homogeneous sets

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