# Unavoidable induced subgraphs in large graphs with no homogeneous sets

## Author(s): Chudnovsky, Maria; Kim, Ringi; Oum, Sang-il; Seymour, Paul D.

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr13g7z`

Abstract: | A homogeneous set of an n-vertex graph is a set X of vertices (2≤|X|≤n−12≤|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+1t+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,nK1,n by subdividing every edge once, (2) the line graph of K2,nK2,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. |

Publication Date: | May-2016 |

Electronic Publication Date: | 10-Feb-2016 |

Citation: | Chudnovsky, Maria, Kim, Ringi, Oum, Sang-il, Seymour, Paul. (2016). Unavoidable induced subgraphs in large graphs with no homogeneous sets. Journal of Combinatorial Theory, Series B, 118 (1 - 12. doi:10.1016/j.jctb.2016.01.008 |

DOI: | doi:10.1016/j.jctb.2016.01.008 |

ISSN: | 0095-8956 |

Pages: | 1 - 12 |

Type of Material: | Journal Article |

Journal/Proceeding Title: | Journal of Combinatorial Theory, Series B |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.