Unavoidable induced subgraphs in large graphs with no homogeneous sets

DOI10.1016/J.JCTB.2016.01.008zbMATH Open1332.05112arXiv1504.05322OpenAlexW3098534285MaRDI QIDQ256979FDOQ256979

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)

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.

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

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

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)

Cites Work

• Graph theory
• Graphs indecomposable with respect to the X-join
• Extension of hereditary classes with substitutions
• Unavoidable doubly connected large graphs
• Normal hypergraphs and the perfect graph conjecture
• Title not available (Why is that?)
• Unavoidable vertex-minors in large prime graphs
• Typical subgraphs of 3- and 4-connected graphs

Cited In (10)

• Title not available (Why is that?)
• Unavoidable subtournaments in large tournaments with no homogeneous sets
• Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
• On unavoidable-induced subgraphs in large prime graphs
• Resolutions of convex geometries
• 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
• 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)