Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $\alpha,\beta\geq2$ and given an optimum vertex coloring is it $\mathsf{NP}$-complete to decide if clique number $\omega(G)>k$?


The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete:

Instance: An integer $k$; a $k$-partite graph $G=(V,E)$
Question: Does $G$ contain a $k$-clique?

Here is a construction that shows NP-completeness of your problem variant:

  • Let $G$ and $k$ be as in the proof in Garey and Johnson
  • Let $H_1$ be a graph on $k+2$ vertices: The $k-3$ vertices $v_1,\ldots,v_{k-3}$ induce a clique, and the five vertices $u_1,\ldots,u_5$ induce an odd cycle $C_5$. Every $u_i$ is connected to every $v_j$. It is easy to see that $\omega(H_1)=k-1$ and $\chi(H_1)=k$.
  • Let $H_2$ be an independent set on $2|V|+2k^2$ vertices.
  • Create a graph $G'$ by taking the disjoint union of $G$, $H_1$ and $H_2$, and by adding all the edges between $H_2$ on the one side and $G\cup H_2$ on the other side.

It can be verified that:

  • $\alpha(G')=2|V|+2k^2$. (Take all vertices in $H_2$.)
  • $\chi(G')=k+1$. (Note that $G\cup H_2$ is $k$-colorable, and that $H_1$ adds one more color.)
  • $\omega(G')=\max\{\omega(G),k-1\}+1$. (Note that $\omega(G\cup H_2)=\max\{\omega(G),k-1\}$, and that $H_1$ adds one more vertex to this.)

Hence the knowledge of $\omega(G')$ would allow us to decide whether $\omega(G)=k$.

  • $\begingroup$ does the problem satisfy both my bounds. Sorry forgot lower bound on $\omega$ and upper bound on $\alpha$. $\endgroup$ – Turbo Oct 24 '16 at 17:20

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.