Complexity of two coloring problems in cubic planar bipartite mixed graphs

Ries, Bernard

Ries, Bernard (2010), Complexity of two coloring problems in cubic planar bipartite mixed graphs, Discrete Applied Mathematics, 158, 5, p. 592-596. http://dx.doi.org/10.1016/j.dam.2009.10.016

Type

Article accepté pour publication ou publié

Date

2010

Nom de la revue

Discrete Applied Mathematics

Volume

158

Numéro

Éditeur

Elsevier

Pages

592-596

Résumé (EN)

In this note we consider previous termtwo coloring problemsnext term in previous termmixed graphs, i.e., graphsnext term containing edges and arcs, which arise from scheduling previous termproblemsnext term where disjunctive and precedence constraints have to be taken into account. We show that they are both View the MathML source-complete in previous termcubic planar bipartite mixed graphs,next term which strengthens some results of Ries and de Werra (2008) [9].

Mots-clés

Mixed graph coloring; List coloring; Bipartite graph; Scheduling; Computational complexity