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

I am trying to determine whether the number of maximal cliques in a graph with no induced $C_{n}\ |\ n>4$ is exponential with respect to the number of vertices.

Is there a paper that mentions such result?

More specifically, my graph is a $(C_5,P_5)$-free graph.

  • 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$ When you have a dominating clique (or a dom. $P_3$), you will also have bounded diameter. Now, roughly speaking, the most you can do is introduce new vertices around the dom. clique, and connect them suitably to the vertices of that clique. So I suspect the num. of maximal cliques remains polynomial in the number of vertices. $\endgroup$ – Juho Nov 18 '19 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.