EXCLUDING A SUBSTAR AND AN ANTISUBSTAR

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.