Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

Question

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

Answer 1

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