Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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