Consider the following communication complexity problem: Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A ``certificate'' for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. A ``clique-stable set separator'' is a set of certificates which contains at least one certificate for each input (K,S). Given a class of graphs, the goal is to know whether there exists, for every graph of the class, a clique-stable set separator with only polynomially many certificates. This question, originally restricted to the case of perfect graphs, occurred to Yannakakis when studying extended formulations of the stable set polytope (a polytope P has a small extended formulation if it is the projection of a polytope Q lying in a higher dimensional space, with a small number of facets). A recent result by Goos provides a super-polynomial lower bound for the class of all graphs, but the case of perfect graphs is still open. We use different techniques to prove that a polynomial clique-stable set separator exists in restricted classes of graphs: probabilistic arguments for random graphs, VC-dimension for graphs where a split graph H is forbidden, the Strong Erdos-Hajnal property for graphs with no induced path on k vertices and its complement, and decomposition by 2-joins for perfect graphs with no balanced skew partition.