The Parameterized Complexity of Coloring Mixed Graphs

Authors: Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, Alexander Wolff

A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring c of a mixed graph G assigns a positive integer to each vertex such that c(u)!=c(v) for every edge {u,v} and c(u)