A note on the maximum ratio between chromatic number and clique number

Abstract

Let $f(n)$ be the maximum, over all graphs $G$ on $n$ vertices, of the ratio $\frac{\ddot{I}‡(G)}{\ddot{I}‰(G)}$, where $\ddot{I}‡(G)$ denotes the chromatic number of $G$ and $\ddot{I}‰(G)$ the clique number of $G$. In 1967, Erdős showed that \[ \Big( \frac{1}{4} +o(1) \Big) \frac{n}{(\log_2 n)^2} \le f(n) \le \big( 4+o(1) \big) \frac{n}{(\log_2 n)^2} .\] We show that \[ f(n) \le \big(c+o(1)\big) \frac{n}{(\log_2 n)^2}\] for some $c<3.72$. This follows from recent improvements in the asymptotics of Ramsey numbers and is the first improvement in the asymptotics of $f(n)$ established by Erdős.

6 pages