A correspondence coloring of a simple graph assigns one color from a list at each vertex while avoiding
specified pairs along its edges. The lists 
are pairwise disjoint finite
sets, and each edge 
carries a matching between 
and 
.
A valid coloring chooses 
so that 
is never an edge of
that matching. This is also called DP coloring (Dvorák
and Postle 2018). Ordinary list coloring is recovered
by matching copies of the same color across adjacent
lists.
For a finite graph 
, the correspondence
chromatic number 
is the least positive
integer 
such that every such assignment with lists of size at least 
has a valid coloring. If
has at least one vertex and maximum
vertex degree 
, then
 |
where 
is the chromatic number and 
is the choice number.
The final bound follows by choosing colors successively, since each previously colored
neighbor forbids at most one list element.
