On the proper orientation number of bipartite graphs

Description

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 prove that it is NP-complete to decide whether − → χ (G) ≤ 3, for planar bipartite graphs G with maximum degree 5.

Abstract

International audience

Additional details