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

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 is linear or polynomial 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 4-cycles are edge-disjoint.

Is there a paper that mentions such result?

• FWIW, every (connected) $P_5$-free has either a dominating clique or a dominating $P_3$. Also, if it helps, the class of $(C_5,P_5)$-free graphs is also known as the class of perfect connected-dominant graphs (i.e., that's the class of graphs for which the domination number equals the connected domination number for every induced subgraph). For a proof of the characterization and more, see Zverovich's 2003 paper "Perfect connected-dominant graphs". – Juho Nov 18 '19 at 10:06
• – Yuval Filmus Oct 11 at 18:54
• @plshelp you seem to be missing the understanding that being X-free means having not X as an induced subgraph. – JimN Oct 12 at 19:35
• I think @Juho 's comments should be enough to solve this. There is a dominating clique (which will be one maximal clique), and a lot of domination properties. For every vertex outside the dominating clique, it forms a maximal clique along with every vertex which dominates it ( since if x dominates y, x's neighbours include all of y's neighbours). – JimN Oct 12 at 19:39
• – D.W. Oct 13 at 2:47

A ($$2C_4$$, $$C_5$$, $$P_5$$)-free graph may have exponentially many maximal cliques. For example, 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$$ appear as an induced subgraph. https://doi.org/10.1007/BF02760024
Note: If the complement of a graph has $$k$$ pairwise independent edges, then they give you $$2^k$$ maximal cliques. Conversely, it is known that the number of maximal cliques is upper-bounded by a function of the maximum number of independent edges in the complement . https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230230308