Ramsey's theorem says that for every clique H1 and for every graph H2 with no edges, all graphs containing neither of H1, H2 as induced subgraphs have bounded order. What if, instead, we exclude a graph H1 with a vertex whose deletion gives a clique, and the complement H2 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.
All Science Journal Classification (ASJC) codes
- Induced subgraphs
- Ramsey's theorem