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

1 Answer 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, 2020 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$ Oct 10, 2020 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, 2020 at 5:25
  • 2
    $\begingroup$ The following paper supports such an intuition. doi.org/10.1002/net.3230230308 $\endgroup$ Oct 11, 2020 at 14:09
  • 1
    $\begingroup$ Done! I posted a slightly expanded answer there. $\endgroup$ Oct 12, 2020 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.