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
Author(s)
Ries, Bernard
Date Issued
2008
Editorial or Peer reviewed
NON-REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
May 9, 2008
Use this identifier to reference this record