The asymptotic behavior of the correspondence chromatic number

Abstract

Alon proved that for any graph $G$, ${\chi }_{\ell }(G)=\Omega (\ln d)$, where ${\chi }_{\ell }(G)$ is the list chromatic number of $G$ and $d$ is the average degree of $G$. Dvořá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)=\Omega (d/\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$ is the maximum degree of $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.

15 pages; a few typos fixed

References in corpus (1)

• The Local Cut Lemma

Cited by in corpus (19)

• Sharp Dirac's Theorem for DP-Critical Graphs
• The Local Cut Lemma
• The Johansson--Molloy Theorem for DP-Coloring
• Asymptotically good edge correspondence colouring
• Cover and variable degeneracy
• Analogue of DP-coloring on variable degeneracy and its applications on list vertex-arboricity and DP-coloring
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Packing list-colourings
• Variable degeneracy on toroidal graphs
• DP-3-coloring of some planar graphs
• The $\chi$-Ramsey problem for triangle-free graphs
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• Fractional DP-Colorings of Sparse Graphs
• Some orientation theorems for restricted DP-colorings of graphs
• On the Chromatic Polynomial and Counting DP-Colorings
• Partial DP-Coloring
• Every planar graph without adjacent cycles of length at most $8$ is $3$-choosable
• Single-conflict colouring