Premium
On DP‐coloring of digraphs
Author(s) -
BangJensen Jørgen,
Bellitto Thomas,
Schweser Thomas,
Stiebitz Michael
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22535
Subject(s) - combinatorics , digraph , list coloring , mathematics , fractional coloring , edge coloring , greedy coloring , complete coloring , vertex (graph theory) , graph coloring , brooks' theorem , discrete mathematics , chromatic scale , graph , graph power , line graph
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 G with a list‐assignment L to finding an independent transversal in an auxiliary graph with vertex set { ( v , c ) | v ∈ V ( G ) , c ∈ L ( 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.