## Complexity of mixed graph coloring

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs. We show that they are both $\mathcal{NP}$-complete in cubic planar bipartite graphs. This answers an open question from \cite{Ries2}.

Published in:
Theoretical Computer Science
Year:
2008
Keywords:
Laboratories: