On-line DP-coloring of graphs

Seog Jin Kim, Alexandr Kostochka, Xuer Li, Xuding Zhu

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)443-453
Number of pages11
JournalDiscrete Applied Mathematics
StatePublished - Oct 15 2020


  • DP-coloring
  • List coloring
  • On-line coloring

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On-line DP-coloring of graphs'. Together they form a unique fingerprint.

Cite this