The asymptotic behavior of the correspondence chromatic number

Alon (2000) proved that for any graph GG, χℓ(G)=Ω(lnd)χℓ(G)=Ω(lnd), where χℓ(G)χℓ(G) is the list chromatic number of GG and dd is the average degree of GG. Dvořák and Postle (2015) recently introduced a generalization of list coloring, which they called correspondence coloring  . We establish an analog of Alon’s result for correspondence coloring; namely, we show that χc(G)=Ω(d/lnd)χc(G)=Ω(d/lnd), where χc(G)χc(G) denotes the correspondence chromatic number of GG. We also prove that for triangle-free GG, χc(G)=O(Δ/lnΔ)χc(G)=O(Δ/lnΔ), where ΔΔ is the maximum degree of GG (this is a generalization of Johansson’s result about list colorings (Johansson, 1996)). This implies that the correspondence chromatic number of a regular triangle-free graph is, up to a constant factor, determined by its degree.