To refer to this page use:
|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.|
|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|
|Pages:||297 - 308|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||SIAM JOURNAL ON DISCRETE MATHEMATICS|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.