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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChudnovsky, Maria-
dc.contributor.authorNorin, Sergey-
dc.contributor.authorReed, Bruce-
dc.contributor.authorSeymour, Paul D.-
dc.date.accessioned2018-07-20T15:09:06Z-
dc.date.available2018-07-20T15:09:06Z-
dc.date.issued2015en_US
dc.identifier.citationChudnovsky, 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/130946113en_US
dc.identifier.issn0895-4801-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr14h4f-
dc.description.abstractRamsey’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.en_US
dc.format.extent297 - 308en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM JOURNAL ON DISCRETE MATHEMATICSen_US
dc.rightsAuthor's manuscripten_US
dc.titleEXCLUDING A SUBSTAR AND AN ANTISUBSTARen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1137/130946113-
dc.date.eissued2015-02-05en_US
dc.identifier.eissn1095-7146-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
Excluding_a_substar_and_an_.pdf141.68 kBAdobe PDFView/Download


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