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).
- List coloring
- On-line coloring
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics