Skip to main content

EXCLUDING A SUBSTAR AND AN ANTISUBSTAR

Author(s): Chudnovsky, Maria; Norin, Sergey; Reed, Bruce; Seymour, Paul D

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr14h4f
Abstract: Ramsey’s theorem says that for every clique H-1 and for every graph H-2 with no edges, all graphs containing neither of H-1, H-2 as induced subgraphs have bounded order. What if, instead, we exclude a graph H-1 with a vertex whose deletion gives a clique, and the complement H-2 of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these.
Publication Date: 2015
Electronic Publication Date: 5-Feb-2015
Citation: Chudnovsky, Maria, Norin, Sergey, Reed, Bruce, Seymour, Paul. (2015). EXCLUDING A SUBSTAR AND AN ANTISUBSTAR. SIAM JOURNAL ON DISCRETE MATHEMATICS, 29 (297 - 308. doi:10.1137/130946113
DOI: doi:10.1137/130946113
ISSN: 0895-4801
EISSN: 1095-7146
Pages: 297 - 308
Type of Material: Journal Article
Journal/Proceeding Title: SIAM JOURNAL ON DISCRETE MATHEMATICS
Version: Author's manuscript



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