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)

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.