Hemanshu Kaul

DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. Intuitively, DP-coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP-coloring of a graph is equivalent to an independent transversal in an auxiliary structure called a DP-cover of .

Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose 0 ≤ ϵ ≤ 1 $0\le \epsilon \le 1$ , G $G$ is a graph, L $L$ is a list assignment for G $G$ , and r $r$ is a function with nonempty domain D ⊆ V ( G ) $D\subseteq V(G)$ such that r ( v ) ∈ L ( v ) $r(v)\in L(v)$ for each v ∈ D $v\in D$ ( r $r$ is called a request of L $L$ ).

The chromatic polynomial of a graph G $G$ , denoted P ( G , m ) $P(G,m)$ , is equal to the number of proper m $m$ -colorings of G $G$ . The list color function of graph G $G$ , denoted P ℓ ( G , m ) ${P}_{\ell }(G,m)$ , is a list analogue of the chromatic polynomial that has been studied since the early 1990s, primarily through comparisons with the corresponding chromatic polynomial.