Abstract
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}.
Details
Title
Complexity of mixed graph coloring
Author(s)
Ries, Bernard
Published in
Theoretical Computer Science
Date
2008
Laboratories
ROSE
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSE - Chair of Operations Research SE
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Work produced at EPFL
Journal Articles
Submitted
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Work produced at EPFL
Journal Articles
Submitted
Record creation date
2008-05-09