  The greedy coloring algorithm shows that a graph of maximum degree at most
$\Delta$ has chromatic number at most $\Delta + 1$, and this is tight for
cliques. Much attention has been devoted to improving this "greedy bound" for
graphs without large cliques. Brooks famously proved that this bound can be
improved by one if $\Delta \geq 3$ and the graph contains no clique of size
$\Delta + 1$. Reed's Conjecture states that the "greedy bound" can be improved
by $k$ if the graph contains no clique of size $\Delta + 1 - 2k$. Johansson
proved that the "greedy bound" can be improved by a factor of
$\Omega(\ln(\Delta)^{-1})$ or
$\Omega\left(\frac{\ln(\ln(\Delta))}{\ln(\Delta)}\right)$ for graphs with no
triangles or no cliques of any fixed size, respectively.
  Notably missing is a $\textit{linear}$ improvement on the "greedy bound" for
graphs without large cliques. In this paper, we prove that for sufficiently
large $\Delta$, if $G$ is a graph with maximum degree at most $\Delta$ and no
clique of size $\omega$, then $$\chi(G) \leq
72\Delta\sqrt{\frac{\ln(\omega)}{\ln(\Delta)}}.$$ This implies that for
sufficiently large $\Delta$, if $\omega^{(72c)^2} \leq \Delta$ then $\chi(G)
\leq \Delta/c$.
  This bound actually holds for the list-chromatic and even the
correspondence-chromatic number (also known as the DP-chromatic number). In
fact, we prove what we call a "local version" of it, a result implying the
existence of a coloring when the number of available colors for each vertex
depends on local parameters, like the degree and the clique number of its
neighborhood. Our result simultaneously implies the linear improvement over the
"greedy bound" and the two aforementioned results of Johansson.
