I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?


It is NP-hard:

Bruno Codenotti, Ivan Gerace, Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra and its Applications 285 (1-3), pages 123-142, 1998, pdf

Other Cayley graphs have been studied by Chris Godsil and Brendan Rooney in the paper Hardness of Computing Clique Number and Chromatic Number For Cayley Graphs, European Journal of Combinatorics 62, pages 147-166, 2017


Your Answer

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

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