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

Journal name

Discrete Applied Mathematics

Volume

158

Number

Publisher

Elsevier

Pages

592-596

Abstract (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].

Subjects / Keywords

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