# Graph classes in which CLIQUE is known to be NP-hard?

Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, it was one of Karp's list of 21 NP-complete problems. My question is:

For what restricted families of graphs is CLIQUE known to be NP-complete?

I could find one such graph class with Google's help: the class of $t$-interval graphs for any $t\ge 3$ (Butman et al., TALG 2010) [1].

Do you know of other graph classes where this problem has been shown to be NP-complete?

[1] Butman, Hermelin, Lewenstein, Rawitz. Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6(2), 2010

• ISGCI is your friend. – Tsuyoshi Ito Nov 26 '10 at 17:58
• @Tsuyoshi Ito - that's a fantastic resource, certainly worthy of answer status. – s8soj3o289 Nov 27 '10 at 2:52
• @blackkettle: It's in the FAQ. – András Salamon Nov 28 '10 at 21:22

The equivalence of CLIQUE on $G$ and INDEPENDENT SET on $\overline{G}$ will perhaps help you find more classes for which the problem remains NP-complete.