<p>The <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture11.pdf">Lovász $\vartheta$ function</a> is an efficiently computable function with the property</p>

<p>$$
\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 <a href="http://www.nada.kth.se/~johanh/cliqueinap.pdf">impossible, unless P=NP</a>.</p>

<p>The above argument is conditional on the conjecture P $\neq$ NP. However, <a href="http://www.wisdom.weizmann.ac.il/~feige/Approx/theta.ps">Feige showed</a> that, unconditionally, there exists a constant $c$ and an infinite family of graphs for which</p>

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

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

CC BY-SA 3.0
2014-02-05T18:16:45.763Z
2014-02-05T22:38:00.553Z
2014-02-05T22:38:00.553Z
Sasho Nikolov
<p>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.</p>

<p>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?</p>

<co.combinatorics><approximation-algorithms><graph-colouring><set-cover><clique>
Worst case ratio between minimum clique cover and maximum independent set
dspyz
# Worst case ratio between minimum clique cover and maximum independent set

(Asked by: username_0 on 2014-02-05)

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?

**Tags:** co.combinatorics, approximation-algorithms, graph-colouring, set-cover, clique

---

## 1 answers

### Answer by username_1 on 2014-02-05. Score: 9 | Accepted answer

The [Lovász $\vartheta$ function](http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture11.pdf) 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](http://www.nada.kth.se/~johanh/cliqueinap.pdf).

The above argument is conditional on the conjecture P $\neq$ NP. However, [Feige showed](http://www.wisdom.weizmann.ac.il/~feige/Approx/theta.ps) 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.


---

