3
$\begingroup$

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?

$\endgroup$
1
8
+50
$\begingroup$

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.

https://doi.org/10.1007/BF02760024

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – padawan Oct 9 '20 at 20:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Yota Otachi Oct 10 '20 at 3:24
  • $\begingroup$ So basically, whenever 4-cycles are involved, it is most likely that the number of maximal cliques is exponential. $\endgroup$ – padawan Oct 10 '20 at 5:25
  • 2
    $\begingroup$ The following paper supports such an intuition. doi.org/10.1002/net.3230230308 $\endgroup$ – Yota Otachi Oct 11 '20 at 14:09
  • 1
    $\begingroup$ Done! I posted a slightly expanded answer there. $\endgroup$ – Yota Otachi Oct 12 '20 at 22:43

Your Answer

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

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