<p>The famous graph (the complement of the disjoint union of <span class="math-container">$n/3$</span> triangles) with <span class="math-container">$3^{n/3}$</span> maximal cliques is <span class="math-container">$K_1 \cup K_2$</span>-free, and thus has none of <span class="math-container">$2C_4$</span>, <span class="math-container">$C_5$</span>, <span class="math-container">$P_5$</span> as an induced subgraph.</p>
<p><a href="https://doi.org/10.1007/BF02760024" rel="noreferrer">https://doi.org/10.1007/BF02760024</a></p>

CC BY-SA 4.0
2020-10-09T20:48:31.437Z
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.
padawan
CC BY-SA 4.0
2020-10-10T03:24:12.830Z
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.
Yota Otachi
CC BY-SA 4.0
2020-10-10T05:25:04.237Z
So basically, whenever 4-cycles are involved, it is most likely that the number of maximal cliques is exponential.
padawan
CC BY-SA 4.0
2020-10-11T14:09:04.513Z
The following paper supports such an intuition.
https://doi.org/10.1002/net.3230230308
Yota Otachi
CC BY-SA 4.0
2020-10-12T12:45:39.463Z
Can you please be kind enough to post this answer here as well? https://cs.stackexchange.com/questions/117238/number-of-maximal-cliques-in-a-2c-4-c-5-p-5-free-graph
I have a bounty going on there and it would be a shame if 100 rep was wasted :)
padawan
CC BY-SA 4.0
2020-10-12T22:43:52.787Z
Done! I posted a slightly expanded answer there.
Yota Otachi
CC BY-SA 4.0
2020-10-09T01:02:25.883Z
2020-10-09T01:02:25.883Z
Yota Otachi
<p>So far, I have found out that chordal graphs have <a href="http://i.stanford.edu/pub/cstr/reports/cs/tr/75/531/CS-TR-75-531.pdf" rel="nofollow noreferrer">linear number of maximal cliques</a> with respect to the number of vertices.
In general case, it is exponential.</p>
<p>I am trying to determine whether the number of maximal cliques in a <span class="math-container">$(2C_4, C_5,P_5)$</span>-free graph with respect to the number of vertices.</p>
<p>In a <span class="math-container">$(2C_4, C_5,P_5)$</span>-free graph, the largest induced cycle is of length 4, and no two induced 4-cycles are edge-disjoint.</p>
<p>Is there a paper that mentions such result?</p>

CC BY-SA 4.0
2020-10-13T02:47:09.410Z
Cross-posted: https://cstheory.stackexchange.com/q/47691/5038, https://cs.stackexchange.com/q/117238/755, https://math.stackexchange.com/q/3856299/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<reference-request><graph-theory><clique>
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
padawan
# Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

(Asked by: username_0 on 2020-10-09)

So far, I have found out that chordal graphs have [linear number of maximal cliques](http://i.stanford.edu/pub/cstr/reports/cs/tr/75/531/CS-TR-75-531.pdf) 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?

**Tags:** reference-request, graph-theory, clique

> **Comments:**
> **username_1**: Cross-posted: https://cstheory.stackexchange.com/q/47691/5038, https://cs.stackexchange.com/q/117238/755, https://math.stackexchange.com/q/3856299/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2020-10-09. Score: 8 | Accepted answer

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>

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: So basically, whenever 4-cycles are involved, it is most likely that the number of maximal cliques is exponential.  
> **username_2**: The following paper supports such an intuition. https://doi.org/10.1002/net.3230230308  
> **username_0**: Can you please be kind enough to post this answer here as well? https://cs.stackexchange.com/questions/117238/number-of-maximal-cliques-in-a-2c-4-c-5-p-5-free-graph I have a bounty going on there and it would be a shame if 100 rep was wasted :)  
> **username_2**: Done! I posted a slightly expanded answer there.  

---

