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

<blockquote>
  <p>Instance: An integer $k$; a $k$-partite graph $G=(V,E)$<br>
  Question: Does $G$ contain a $k$-clique?</p>
</blockquote>

<p>Here is a construction that shows NP-completeness of your problem variant:</p>

<ul>
<li>Let $G$ and $k$ be as in the proof in Garey and Johnson</li>
<li>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$.</li>
<li>Let $H_2$ be an independent set on $2|V|+2k^2$ vertices.</li>
<li>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. </li>
</ul>

<p>It can be verified that:</p>

<ul>
<li>$\alpha(G')=2|V|+2k^2$. (Take all vertices in $H_2$.)</li>
<li>$\chi(G')=k+1$. (Note that $G\cup H_2$ is $k$-colorable, and that $H_1$ adds one more color.)</li>
<li>$\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.)</li>
</ul>

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

CC BY-SA 3.0
2016-10-24T17:20:07.290Z
does the problem satisfy both my bounds. Sorry forgot lower bound on $\omega$ and upper bound on $\alpha$.
Turbo
CC BY-SA 3.0
2016-10-24T11:57:03.013Z
2016-10-24T11:57:03.013Z
Gamow
<p>Given a $k&gt;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)&gt;k$? </p>

<graph-algorithms><np-complete><graph-colouring><clique><independent-set>
Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
Turbo
# Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

(Asked by: username_0 on 2016-10-24)

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$?

**Tags:** graph-algorithms, np-complete, graph-colouring, clique, independent-set


---

## 1 answers

### Answer by username_1 on 2016-10-24. Score: 5

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$.

> **Comments:**
> **username_0**: does the problem satisfy both my bounds. Sorry forgot lower bound on $\omega$ and upper bound on $\alpha$.  

---

