Worst case ratio between minimum clique cover and maximum independent set
The Lovász $\vartheta$ function is an efficiently computable function with the property

$$
\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),
$$
where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon &gt; 0$, then we would have an efficient approximation to $\alpha(G)$ within a factor of $n^{1-\varepsilon}$ . However, this is impossible, unless P=NP.

The above argument is conditional on the conjecture P $\neq$ NP. However, Feige showed that, unconditionally, there exists a constant $c$ and an infinite family of graphs for which

$$
\alpha(G) \leq \vartheta(G) &lt; 2^{\sqrt{\log n}}\\
\bar{\chi}(G) &gt; \frac{n}{2^{c\sqrt{\log n}}}
$$

So the gap between $\alpha(G)$ and $\bar{\chi}(G)$ is $n^{1 - o(1)}$, no need for conjectures.