The complexity of the proper orientation number

A proper orientation of a graph G = (V, E) is an orientation D of E(G) such that for every two adjacent vertices v and u, d((D) over bar)(v) not equal d((D) over bar)(u) where d((D) over bar)(v) is the number of edges with head v in D. The proper orientation number of G is defined as (chi) over right arrow (G) = min(D is an element of Gamma) max(v is an element of v)(G)d((D) over bar)(v) where Gamma is the set of proper orientations of G. We have chi(G) 1 <= (chi) over right arrow (G) <= Delta(G), where chi(G) and Delta(G) denote the chromatic number and the maximum degree of G, respectively. We show that, it is NP-complete to decide whether (chi) over right arrow (G) = 2, for a given planar graph G. Also, we prove that there is a polynomial time algorithm for determining the proper orientation number of 3-regular graphs. In sharp contrast, we will prove that this problem is NP-hard for 4-regular graphs. (C) 2013 Elsevier B.V. All rights reserved.