# 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?

• Look into "$\chi$-boundedness" which is an area studied by folks like Paul Seymour and Maria Chudnovsky. Feb 22, 2017 at 19:54
• This isn't relevant: all the graph classes which are conjectured (or known) to be $\chi$-bounded are also conjectured or known to have the Erdos-Hajnal property; which in particular means they have only polynomially many vertices in $\max(\alpha(G),\omega(G))$, not exponentially many as for Ramsey graphs or the graphs Paul is interested in. Also, Paul is one of the 'folks like...'. Feb 23, 2017 at 23:01

I guess you meant to write $\chi(G)\le\frac{\sqrt{2}^{\alpha(G)}+\sqrt{2}^{\omega(G)}}{r(G)}$ in your edit.
I think it's (somewhat) commonly believed that the $\sqrt{2}^k$ lower bound on $R(k,k)$ is far from optimal. In some sense, the large cliques that mean the random graph 'only' gives this lower bound are sporadic; there probably should exist a quasirandom construction which doesn't have any such large cliques; this line of thinking would get to a $2^k$ lower bound on Ramsey numbers, which (I think) is likely the truth (more or less); of course I have no idea how to prove anything. However, such a graph would still have chromatic number of order $n/\log n$; more accurately, its chromatic number would be about twice that of the random graph on the same number of vertices. So that would raise the bar: the best you can hope for is then $\chi(G)\le \frac{2^{\alpha(G)}+2^{\omega(G)}}{r(G)}$.
On the other side, you can get a little improvement over the $\chi(G)\le 4^{\alpha(G)}+4^{\omega(G)}$ which corresponds to simply colouring every vertex differently. Namely, since we know somewhat stronger bounds on off-diagonal Ramsey numbers, colour instead by taking sequentially maximum independent sets, and if these are not of order $\log n$ then the $4^{\omega(G)}$ term will be much larger than $v(G)$; so we gain a log factor.
• What you wrote is untrue beacuse of the example of a random graph with probability $\frac{1}{2}$ that he gave. The chromatic number is $n/\log{n}$, and the right side in your first inequality is something like $\sqrt{n}$. Feb 24, 2017 at 9:40
• $G(n,1/2)$ has clique number asymptotically $2\log n$, which is of the order $\log n$ (as Ben Barber points out) but the factor $2$ is important here. Feb 25, 2017 at 21:15