Generalized DP-colorings of graphs

Alexandr V. Kostochka, Thomas Schweser, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number113186
JournalDiscrete Mathematics
Volume346
Issue number11
DOIs
StatePublished - Nov 2023

Keywords

  • Brooks' theorem
  • DP-coloring
  • Degeneracy
  • Generalized coloring of graphs
  • List-coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Generalized DP-colorings of graphs'. Together they form a unique fingerprint.

Cite this