Subdivided Claws and the Clique-Stable Set Separation Property

Let $$ {\mathscr{C}} $$ C be a class of graphs closed under taking induced subgraphs. We say that $$ {\mathscr{C}} $$ C has the clique-stable set separation property if there exists $$ c \in {\mathbb{N}} $$ c ∈ N such that for every graph $$ G \in {\mathscr{C}} $$ G ∈ C there is a collection $$ {\mathscr{P}} $$ P of partitions (X, Y) of the vertex set of G with | $$ {\mathscr{P}}$$ P | ≤ |V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = $$ \emptyset$$ ∅ , then there is (X, Y) ∊ $$ {\mathscr{P}}$$ P with K ⊆ X and S ⊆ Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families $$ {\mathscr{S}}, {\mathscr{K}}$$ S , K of graphs and show that for every S ∊ $$ {\mathscr{S}}$$ S and K ∊ $${\mathscr{K}}$$ K , the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.