A splitter theorem for induced subgraphs

A homogeneous set in a graph G is a subset X of V(G), such that
no vertex of V(G)\X has both a neighbor and a non-neighbor in X. Let us
say that a graph is prime if it has no  homogeneous set X with
1<|X|<|V(G)|. 

Seymour's well-known splitter theorem states that if G and H are
3-connected graphs, G is not a wheel, H is not the complete graph on
four vertices, and H is a minor of G, then G can be built from H by
undeleting or uncontracting one edge at a time, and so that all the
graphs constructed along the way are 3-connected. We prove a similar
result for the induced subgraph containment relation, replacing
3-connected with prime, undeleting and uncontracting with adding a
vertex, and wheels with a certain family of bipartite graphs that we
call B.  We prove that if G and H are prime graphs, G is not in B, and H
is an induced subgraph of G, then G can be built from H, adding one
vertex at a time, and so that all the graphs constructed along the way
are prime.

We then use this result to prove that every n-vertex prime claw-free
graph has at most n+1 simplicial cliques (a clique C of G is simplicial
if for every vertex c of C, the set of neighbors of c outside of C is a
clique). This allows us to test in polynomial time if a claw-free graph
has a simplicial clique, answering a question of Prasad Tetali.

This is joint work with Paul Seymour.