Journal article

Complexity of two coloring problems in cubic planar bipartite mixed graphs

    2010
Published in:
  • Discrete Applied Mathematics. - 2010, vol. 158, no. 5, p. 592-596
English In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307706
Statistics

Document views: 7 File downloads:
  • coloringmixedgraphsiii.pdf: 1