Unavoidable induced subgraphs in large graphs with no homogeneous sets

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

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


A homogeneous set of an n-vertex graph is a set X of vertices (2≤|X|≤n-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 K1,n by subdividing every edge once, (2) the line graph of K2,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.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalJournal of Combinatorial Theory. Series B
StatePublished - May 1 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Induced subgraph
  • Modular decomposition
  • Prime graph
  • Ramsey


Dive into the research topics of 'Unavoidable induced subgraphs in large graphs with no homogeneous sets'. Together they form a unique fingerprint.

Cite this