2
$\begingroup$

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison to the general case: for example 4-hole free odd-signable graphs have at most $|V|+2|E|$ maximal cliques.

Is it known a similar (not to say as tight as) upper-bound on the number of maximal cliques for other hereditary classes of graphs ? In particular, is it already known an improved (w.r.t. $3^{|V|/3}$) upper bound for perfect graphs, claw-free graphs or odd-hole free graphs ?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Cographs form a subclass of perfect graphs and there are examples of cographs with an exponential number of cliques. For example, consider the complement of a perfect matching on $n$ vertices. It is easy to see that this graph is a cograph (hence perfect) and claw-free, but still it has exactly $2^{n/2}$ vertices. I'm not aware of any upper bound for the number of maximal cliques on these classes, but this example shows that one, if exists, must be exponential on the number of vertices.

Improve this answer
$\endgroup$
2
$\begingroup$

Chordal graphs: at most $n$

Graphs of boxicity $k$: at most $(2n)^k$

Planar graphs: at most $\dfrac {7n} 3 - 6$

$K_t$-free, $t \geq 2$: at most $\max \left\{n, n \dfrac {\Delta^{n-2}} {2^{t-2}} \right\}$, with $\Delta$ being the maximum degree of any vertex in the graph.

See the paper "Complexity Results on Graphs with Few Cliques" by B. Rosgen and L. Stewart.

Improve this answer
$\endgroup$
0
$\begingroup$

The Moon-Moser lower bound graphs are complete partite (with parts of size mainly 3) and are perfect.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .