Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle).

Are there graph problems that can be solved in polynomial time for $C$ other than Clique and Clique cover?

If I remember correctly, this is impossible for independent set (unless $P=NP$).

Search in graphclasses.org didn't find any.

A class for which Clique and Clique cover are polynomial is (C5,C6,X164,X165,sunlet4,triangle)-free


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.