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:




 Record created 2008-05-09, last modified 2018-07-07


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)