Name
Abstract | ||
|---|---|---|
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 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jctb.2016.01.008 | Journal of Combinatorial Theory Series B |
Keywords | Field | DocType |
Modular decomposition,Induced subgraph,Prime graph,Ramsey | Discrete mathematics,Wheel graph,Block graph,Combinatorics,Circulant graph,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Factor-critical graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
118 | C | J. Combin. Theory, Ser. B, 118(May 2016), pp. 1-12 |
Citations | PageRank | References |
2 | 0.51 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| ringi kim | 2 | 7 | 2.96 |
| Sang-il Oum | 3 | 668 | 37.80 |
| Paul Seymour | 4 | 4 | 0.89 |