# Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

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.

Michael R. Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann: Graph-based data clustering with overlaps. Discret. Optim. 8(1): 2-17 (2011)

• Do you have the minimal forbidden subgraphs for s = 2 or 3? (I know that the only one is $P_3$ when s = 1.) – Yixin Cao Nov 29 '20 at 14:51