7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Look into "$\chi$-boundedness" which is an area studied by folks like Paul Seymour and Maria Chudnovsky. $\endgroup$ – Pat Devlin Feb 22 '17 at 19:54
  • $\begingroup$ 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...'. $\endgroup$ – user36212 Feb 23 '17 at 23:01
1
$\begingroup$

This is not really an answer, but too long for a comment.

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – karpasi Feb 24 '17 at 9:40
  • 2
    $\begingroup$ $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. $\endgroup$ – user36212 Feb 25 '17 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.