On DP-coloring of digraphs |
| |
Authors: | Jørgen Bang-Jensen Thomas Bellitto Thomas Schweser Michael Stiebitz |
| |
Affiliation: | 1. IMADA, University of Southern Denmark, Odense M, Denmark;2. Institute of Mathematics, Technische Universität Ilmenau, Ilmenau, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Brooks’ theorem digraph coloring DP-coloring list-coloring |
|
|