TY - JOUR
T1 - Generalized DP-colorings of graphs
AU - Kostochka, Alexandr V.
AU - Schweser, Thomas
AU - Stiebitz, Michael
N1 - Funding Information:
Research of this author is supported in part by the Simons Visiting Professor Grant, by NSF RTG Grant DMS-1937241 and grant 19-01-00682 of the Russian Foundation for Basic Research.
Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022
Y1 - 2022
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.
KW - Brooks' theorem
KW - DP-coloring
KW - Degeneracy
KW - Generalized coloring of graphs
KW - List-coloring
UR - http://www.scopus.com/inward/record.url?scp=85139015394&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85139015394&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2022.113186
DO - 10.1016/j.disc.2022.113186
M3 - Article
AN - SCOPUS:85139015394
SN - 0012-365X
VL - 346
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 11
M1 - 113186
ER -