论文标题
分开在线和离线DP-Chromation数字
Separating the online and offline DP-chromatic numbers
论文作者
论文摘要
DP颜色的问题是对列表颜色问题的概括，在该问题中，目标是在图$ g $的某个拓扑封面中找到独立的横向。在在线DP彩色问题中，$ G $的封面一次被揭示出一个组件，并且必须根据不完整的信息在零件中构建封面的独立横向。 Kim，Kostochka，Li和Zhu询问与这两个图形着色问题相对应的色数是否在单个图中任意差异很大。我们通过构造图形来回答这个问题，在线DP-Chromation编号和离线DP-Chromation数字之间的差距是任意较大的。
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. Kim, Kostochka, Li, and Zhu 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.
