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?

  • 1
    $\begingroup$ 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". $\endgroup$ – Juho Nov 18 '19 at 10:06
  • $\begingroup$ Also on Mathematics: math.stackexchange.com/questions/3856299/… $\endgroup$ – Yuval Filmus Oct 11 at 18:54
  • $\begingroup$ @plshelp you seem to be missing the understanding that being X-free means having not X as an induced subgraph. $\endgroup$ – JimN Oct 12 at 19:35
  • $\begingroup$ 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). $\endgroup$ – JimN Oct 12 at 19:39

(Answered also on https://cstheory.stackexchange.com/questions/47691/)

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

| cite | improve this answer | |
  • $\begingroup$ Thank you for posting your answer here. This is a very useful answer (including the comment discussions at TCS.SE) for my ongoing study. In case you wonder the reason that I stumbled upon this problem; it is about a combinatorial problem about disk intersection graphs. Please do not hesitate to ask for a detailed explanation in detail. $\endgroup$ – padawan Oct 13 at 0:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.