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

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|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.