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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.