MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the question is interesting only if the degree is at least n/2). You could also ask the same question for say regular graphs of degree 3n/4.

share|cite|improve this question
There is lots of information (though not an answer to your exact question) at – Hugh Thomas Jun 24 '14 at 4:06

Let $G = (V,E)$ be a graph and $c ≤ |V |$ a positive integer. The independent sets of $G$ are precisely the cliques of the complementary graph $\overline{G}$.


INSTANCE: Graph $G=(V,E)$, positive integer $c$.

QUESTION: Does $G$ contain an independent set of size $c$ or more,

The independent set problem remains NP-complete when restricted to 3-regular planar graphs.


COMPUTERS AND Intractability, A Guide to the Theory of NP-Completeness

Michael R. Garey / David S. Johnson

page 194-195

share|cite|improve this answer
This answers the question for cliques of specified size, but it doesn't answer it for cliques of size n/2. 3-regular graphs have an independent set of size $n/2$ iff they are bipartite. – Brendan McKay Jun 25 '14 at 19:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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