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.
