1
$\begingroup$

For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are known?

$\endgroup$

1 Answer 1

10
$\begingroup$

I'll restrict attention to graphs on $n$ vertices and call your parameter $X$. The numerator is at least some multipe of $\log n$ by Ramsey's theorem, and the denominator is at most $n$, so $X \geq \log n /n$. But the random graph $G_{n,1/2}$ has clique and independence number order $\log n$ and chromatic number order $n/\log n$, so $X \leq (\log n)^2/n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .