Journal article

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}.


  • There is no available fulltext. Please contact the lab or the authors.

Related material