DE REZENDE , Susanna

An orientation of a graph G is a digraph D obtained from G by replacing each edge by exactly one of the two possible arcs with the same endvertices. We then prove that deciding whether − → χ (G) ≤ ∆(G) − 1 is an NP-complete problem. We also show that it is NP-complete to decide whether − → χ (G) ≤ 2, for planar subcubic graphs G. Moreover, we...