The rate of growth of the minimum clique size of graphs of given order and chromatic number

Abstract

Let $Q(n,c)$ denote the minimum clique number over graphs with $n$ vertices and chromatic number $c$. We determine the rate of growth of of the sequence ${Q(n,\lceil rn\rceil )}_{n=1}^{\infty }$ for any fixed $0<r\le 1$. We also give a better upper bound for $Q(n,\lceil rn\rceil )$.