The asymptotic behavior of the correspondence chromatic number

Alon proved that for any graph $G$, ${\chi }_{\mathrm{\ell }}(G)=\mathrm{\Omega }(\ln d)$, where ${\chi }_{\mathrm{\ell }}(G)$ is the list chromatic number of $G$ and $d$ is the average degree of $G$. Dvo\v{r}'{a}k and Postle recently introduced a generalization of list coloring, which they called correspondence coloring. We establish an analogue of Alon’s result for correspondence coloring; namely, we show that ${\chi }_c(G)=\mathrm{\Omega }(d\mathrm{/}\ln d)$, where ${\chi }_c(G)$ denotes the correspondence chromatic number of $G$. We also prove that for triangle-free $G$, $\chi_c(G) = O(\Delta/\ln \Delta)$,where$\Delta$isthemaximumdegreeof$G$ (this is a generalization of Johansson’s result about list colorings). This implies that the correspondence chromatic number of a regular triangle-free graph is, up to a constant factor, determined by its degree.