TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Kostochka, Alexandr V.
A1  - Schweser, Thomas
A1  - Stiebitz, Michael
T1  - Generalized DP-colorings of graphs
JF  - Discrete Mathematics
N2  - In the present paper we extend the following three coloring concepts for the class of finite undirected graphs having multiple edges but no loops. First of all, the generalized coloring concept, in which the same colored vertices of a graph induce a subgraph satisfying a prescribed graph property. Secondly, the concept of variable degeneracy, which was introduced by Borodin, Kostochka and Toft in 2000; this makes it possible to give a common generalization of the point partition number and the list chromatic number. Finally, the DP-coloring concept as introduced by Ďvorák and Postle in 2018, where a list assignment of a graph is replaced by a cover. Combining these three coloring concepts leads to generalizations of various classical coloring results, including the theorems of Brooks, of Gallai, and of Erdős, Rubin and Taylor. Our main result is a DP-version of a theorem about partitions of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin, Kostochka, and Toft.
AB  - In the present paper we extend the following three coloring concepts for the class of finite undirected graphs having multiple edges but no loops. First of all, the generalized coloring concept, in which the same colored vertices of a graph induce a subgraph satisfying a prescribed graph property. Secondly, the concept of variable degeneracy, which was introduced by Borodin, Kostochka and Toft in 2000; this makes it possible to give a common generalization of the point partition number and the list chromatic number. Finally, the DP-coloring concept as introduced by Ďvorák and Postle in 2018, where a list assignment of a graph is replaced by a cover. Combining these three coloring concepts leads to generalizations of various classical coloring results, including the theorems of Brooks, of Gallai, and of Erdős, Rubin and Taylor. Our main result is a DP-version of a theorem about partitions of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin, Kostochka, and Toft.
Y1  - 2025
SN  - 0012-365X
SS  - 0012-365X
U6  - https://doi.org/10.1016/j.disc.2022.113186
DO  - https://doi.org/10.1016/j.disc.2022.113186
VL  - 346
IS  - 11
AR  - 113186
S2  - 113186
SP  - 20
PB  - Elsevier BV
ER  -