Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced subgraphs of this property.
In a paper on this topic [1], we showed that given a graph which violates the $s$-vertex overlap property, one can compute a subgraph with $O(s^2)$ vertices that still violates the property in polynomial time as follows: Find a vertex $v$ that is contained in at least $s+1$ maximal cliques. This can be done in polynomial time using a polynomial delay clique enumeration algorithm. Choose $s+1$ of these maximal cliques. Then, choose for each pair of maximal cliques $A$ and $B$ a pair of vertices that witnesses that these maximal cliques are distinct. Altogether, we choose at most ${s+1 \choose 2} + 1 = O(s^2)$ vertices.
My question: Is this implicitly given characterization tight with respect to $s$? Or is there a forbidden subgraph characterization for example with $O(s)$ vertices?
Observe that there are minimal forbidden subgraphs with $s+2$ vertices, for example when $v$ is the center of a star with $s+1$ leaves. It may be easier to think about the property without the vertex $v$, then we are asking for minimal forbidden induced subgraphs for the graph property of having at most $s$ maximal cliques.
