On DP‐coloring of digraphs

  • DP‐coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list‐colorings of (undirected) graphs. It transforms the problem of finding a list‐coloring of a given graph with a list‐assignment to finding an independent transversal in an auxiliary graph with vertex set . In this paper, we extend the definition of DP‐colorings to digraphs using the approach from Neumann‐Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP‐chromatic number, which extends various results on the (list‐)chromatic number of digraphs.

Export metadata

Metadaten
Author:Jørgen Bang‐JensenORCID, Thomas Bellitto, Thomas SchweserORCID, Michael Stiebitz
DOI:https://doi.org/10.1002/jgt.22535
ISSN:0364-9024
Parent Title (English):Journal of Graph Theory
Publisher:Wiley
Document Type:Article (peer reviewed)
Language:English
Publication Year:2019
Release Date:2025/07/17
Volume:95
Issue:1
Page Number:23
First Page:76
Last Page:98
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.