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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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

Improve this answer
$\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$
    – Yota Otachi
    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$
    – Yota Otachi
    Oct 11, 2020 at 14:09
  • 1
    $\begingroup$ Done! I posted a slightly expanded answer there. $\endgroup$
    – Yota Otachi
    Oct 12, 2020 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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