# Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential.

I am trying to determine whether the number of maximal cliques in a $$(2C_4, C_5,P_5)$$-free graph with respect to the number of vertices.

In a $$(2C_4, C_5,P_5)$$-free graph, the largest induced cycle is of length 4, and no two induced 4-cycles are edge-disjoint.

Is there a paper that mentions such result?

• – D.W.
Oct 13, 2020 at 2:47

The famous graph (the complement of the disjoint union of $$n/3$$ triangles) with $$3^{n/3}$$ maximal cliques is $$K_1 \cup K_2$$-free, and thus has none of $$2C_4$$, $$C_5$$, $$P_5$$ as an induced subgraph.
• Thanks for the answer. Do you know whether it is still exponential when two induced triandlges cannot be edge-disjoint in the complement, i.e. $(K_{3,3}, 2C_4, C_5, P_5)$-free? I guess the answer is still yes, but I cannot see it directly. Oct 9, 2020 at 20:48
• As you guessed, the answer is still yes. The complement of the disjoint union of $n/2$ copies of $K_2$'s has $2^{n/2}$ maximal cliques. Oct 10, 2020 at 3:24