On-line DP-coloring of graphs

On-line list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, χ_P(G), (the minimum number of colors needed for an on-line coloring of G) and the DP-chromatic number, χ_DP(G), (the minimum number of colors needed for a DP-coloring of G) is at least the list chromatic number of G and can be much larger. On the other hand, each of them has a number of useful properties. The main goal of the paper is to introduce a common generalization, on-line DP-coloring, of on-line list coloring and DP-coloring and to study its properties. It turns out that many upper bounds on the DP-chromatic number are also upper bounds on the on-line DP-chromatic number. On the other hand, we show that this invariant of a graph can be larger than each of the DP-chromatic number and the paint number. As a biproduct we present examples of graphs G with χ_P(G)>χ_DP(G).