Skip to main content
2 of 3
added 524 characters in body

Bounding chromatic number by a function of independence and clique number

Ramsey's theorem tells us that every graph on $n$ vertices has either a clique or independent subgraph of size at least $\frac{1}{2}\log n$, and so, $|V(G)| \le 4^{\alpha(G)} + 4^{\omega(G)}$ where $\alpha$ and $\omega$ are the maximum size of an independent set and clique subgraph, respectively.

If we only want to bound the chromatic number of $G$, can we get a better bound as a function of $\alpha$ and $\omega$ (than what you get from the Ramsey bound)? Specifically, is it true that for all graphs, $\chi(G) = o(\sqrt2^{\alpha(G)} + \sqrt2^{\omega(G)})$?

Edit:

A closely related question has already been asked: Relationship of clique, independence, and chromatic numbers. Ben Barber pointed out there that the random graph on $n$ vertices has both clique number and independence number on the order of $\log n$ and chromatic number on the order of $n / \log n$. Thus, if we let $r(G) = \alpha(G) + \omega(G)$, the best possible result one could hope for would be $\chi(G) \le \frac{\sqrt2^{r(G)}}{r(G)}$. Could this be true?