MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question was first asked here: cstheory.stackexchange...

Here we want to count the number of independent sets of a comparability graph. For Δ(G)=2 , i.e. the maximum degree of a vertex in G is 2, the number of independent sets can be found in linear time. For Δ(G)=4 , the problem is very hard (#P-complete ?). Take for example the grid graph.

I am wondering about the case of Δ(G)=3 . It seems that it is very simple.

Thank you for your advice/comments in advance. :-)

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.