On the semi-proper orientations of graphs

Description

A weighted orientation of a graph G is a pair (D, w) where D is an orientation of G and w is an arc-weighting of D, that is an application A(D) → N \ {0}. The in-weight of a vertex v in a weighted orientation (D, w), denoted by S (D,w) (v), is the sum of the weights of arcs with head v in D. A semi-proper orientation is a weighted orientation such that two adjacent vertices have different in-weights. The semiproper orientation number of a graph G, denoted by − → χs(G), is min (D,w)∈Γ max v∈V (G) S (D,w) (v), where Γ is the set of all semi-proper orientations of G. A semi-proper orientation (D, w) of a graph G is optimal if max v∈V (G) S (D,w) (v) = − → χs(G). In this work, we show that every graph G has an optimal semi-proper orientation (D, w) such that the weight of each arc is 1 or 2. We then give some bounds on the semi-proper orientation number: we show Mad(G) 2 ≤ − → χs(G) ≤ Mad(G) 2 +χ(G)−1 and δ * (G)+1 2 ≤ − → χs(G) ≤ 2δ * (G) for all graph G, where Mad(G) and δ * (G) are the maximum average degree and the degeneracy of G, respectively. We then deduce that the maximum semi-proper orientation number of a tree is 2, of a cactus is 3, of an outerplanar graph is 4, and of a planar graph is 6. Finally, we consider the computational complexity of associated problems: we show that determining whether − → χs(G) = χ(G) is NP-complete for planar graphs G with − → χs(G) = 2; we also show that deciding whether − → χs(G) ≤ 2 is NP-complete for planar bipartite graphs G.

Abstract

International audience

Additional details