Separating the online and offline DP-chromatic numbers (Q6117242)

Summary: The DP-coloring problem is a generalization of the list-coloring problem in which the goal is to find an independent transversal in a certain topological cover of a graph \(G\). In the online DP-coloring problem, the cover of \(G\) is revealed one component at a time, and the independent transversal of the cover must be constructed in parts based on incomplete information. \textit{S.-J. Kim} et al. [Discrete Appl. Math. 285, 443--453 (2020; Zbl 1447.05086)] asked whether the chromatic numbers corresponding to these two graph coloring problems can have an arbitrarily large difference in a single graph. We answer this question in the affirmative by constructing graphs for which the gap between the online DP-chromatic number and the offline DP-chromatic number is arbitrarily large.