Minimum clique number, chromatic number, and Ramsey numbers

Gaku Liu

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

Let $Q(n,c)$ denote the minimum clique number over graphs with $n$ vertices and chromatic number $c$. We investigate the asymptotics of $Q(n,c)$ when $n/c$ is held constant. We show that when $n/c$ is an integer $\alpha$, $Q(n,c)$ has the same growth order as the inverse function of the Ramsey number $R(\alpha+1,t)$ (as a function of $t$). Furthermore, we show that if certain asymptotic properties of the Ramsey numbers hold, then $Q(n,c)$ is in fact asymptotically equivalent to the aforementioned inverse function. We use this fact to deduce that $Q(n,\lceil n/3 \rceil)$ is asymptotically equivalent to the inverse function of $R(4,t)$.

Détail

DOI : 10.37236/2125

Classification : 05C35, 05C69, 05C55, 05D10
Mots-clés : asymptotic properties of the Ramsey numbers