DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chudnovsky, Maria | ko |
dc.contributor.author | Kim, Ringi | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.contributor.author | Seymour, Paul | ko |
dc.date.accessioned | 2016-06-30T00:32:27Z | - |
dc.date.available | 2016-06-30T00:32:27Z | - |
dc.date.created | 2016-02-08 | - |
dc.date.created | 2016-02-08 | - |
dc.date.created | 2016-02-08 | - |
dc.date.issued | 2016-05 | - |
dc.identifier.citation | JOURNAL OF COMBINATORIAL THEORY SERIES B, v.118, pp.1 - 12 | - |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://hdl.handle.net/10203/208636 | - |
dc.description.abstract | 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. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.title | Unavoidable induced subgraphs in large graphs with no homogeneous sets | - |
dc.type | Article | - |
dc.identifier.wosid | 000372764500001 | - |
dc.identifier.scopusid | 2-s2.0-84961198878 | - |
dc.type.rims | ART | - |
dc.citation.volume | 118 | - |
dc.citation.beginningpage | 1 | - |
dc.citation.endingpage | 12 | - |
dc.citation.publicationname | JOURNAL OF COMBINATORIAL THEORY SERIES B | - |
dc.identifier.doi | 10.1016/j.jctb.2016.01.008 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.nonIdAuthor | Chudnovsky, Maria | - |
dc.contributor.nonIdAuthor | Kim, Ringi | - |
dc.contributor.nonIdAuthor | Seymour, Paul | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Modular decomposition | - |
dc.subject.keywordAuthor | Induced subgraph | - |
dc.subject.keywordAuthor | Prime graph | - |
dc.subject.keywordAuthor | Ramsey | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.