Complexity of two coloring problems in cubic planar bipartite mixed graphs
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
2010Nom de la revue
Discrete Applied MathematicsVolume
158Numéro
5Éditeur
Elsevier
Pages
592-596
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Ries, BernardRé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 complexityPublications associées
Affichage des éléments liés par titre et auteur.
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié
-
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
-
de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié