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

- Publisher
- ACADEMIC PRESS INC ELSEVIER SCIENCE

- Issue Date
- 2016-05

- Language
- English

- Article Type
- Article

- Citation
JOURNAL OF COMBINATORIAL THEORY SERIES B, v.118, pp.1 - 12

- ISSN
- 0095-8956

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.