Worst case ratio between minimum clique cover and maximum independent set

Question

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices which are part of the independent set must belong to separate cliques in the clique cover.

Is there any way to put a worst case (hopefully constant) upper bound on the ratio between these two values? What about when the number of vertices grows large? I know it must be at least $\frac{3}{2}$, since we can have a graph composed of an arbitrary number of pentagons (each pentagon has a maximum independent set of 2 vertices, but a minimum clique cover of 3 cliques). Can anyone find a graph where the ratio is larger than $\frac{3}{2}$? larger than 2?

Answer 1

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 > 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) < 2^{\sqrt{\log n}}\\ \bar{\chi}(G) > \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.