Complexity of mixed graph coloring
Bernard Ries · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2008
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}.