On DP-Coloring of Digraphs

DOI10.1002/JGT.22535MaRDI QIDQ6311566arXivWikidataFDO

Authors Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz

Publication date 23 December 2018

Published in arXiv

Full work available at URL https://doi.org/10.1002/JGT.22535

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

arXiv classification

math.CO

Abstract: DP-coloring is a relatively new coloring concept by Dvov{r}'ak 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 $G$ with a list-assignment $L$ to finding an independent transversal in an auxiliary graph with vertex set $(v,c)|vinV(G),cinL(v)$. 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.

This page was built for publication: On DP-Coloring of Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311566)