Loading...
preprint
Complexity of mixed graph coloring
Ries, Bernard
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}.
Type
preprint
Authors
Ries, Bernard
Publication date
2008
Peer reviewed
NON-REVIEWED
EPFL units
Available on Infoscience
May 9, 2008
Use this identifier to reference this record