Subdivided Claws and the Clique-Stable Set Separation Property

Abstract

Let $\mathcal{C}$ be a class of graphs closed under taking induced subgraphs. We say that $\mathcal{C}$ has the {\em clique-stable set separation property} if there exists $c\in \mathbb{N}$ such that for every graph $G\in \mathcal{C}$ there is a collection $\mathcal{P}$ of partitions $(X,Y)$ of the vertex set of $G$ with $|\mathcal{P}|\le |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\cap S=\varnothing$, then there is $(X,Y)\in \mathcal{P}$ with $K\subseteq X$ and $S\subseteq 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 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 $\mathcal{S},\mathcal{K}$ of graphs and show that for every $S\in \mathcal{S}$ and $K\in \mathcal{K}$, the class of graphs with no induced subgraph isomorphic to $S$ or $K$ has the clique-stable set separation property.