Abstract

An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G, denoted by (chi) over right arrow (G), is the minimum k such that G has a proper k-orientation. 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 A(D) -> N {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such that for every two adjacent vertices u and v in G, we have that S-(D,S-w)(v) not equal S-(D,S-w)(u), where S-(D,S-w)(v) is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper k-orientation (D, w) of a graph G is a semi-proper orientation of G such that max(v is an element of V)(G) S-(D,S-w)(v) <== k. The semi-proper orientation number of a graph G, denoted by (chi) over right arrow (s)(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that (chi) over right arrow (s)(G) is an element of {omega(G) - 1, omega(G)} for every split graph G, and that, given a split graph G, deciding whether (chi) over right arrow (s)(G) = omega(G) - 1 is an NP-complete problem. We also show that, for every k, there exists a (chordal) graph G and a split subgraph H of G such that (chi) over right arrow (G) = k and (chi) over right arrow (H) = 2k - 2. In the sequel, we show that, for every n >= p(p + 1), (chi) over right arrow (s)(P-n(p)) = inverted right perpendicular 3/2p inverted left perpendicular, where P-n(p) is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that ??(G) = 3 for any unit interval graph G with (chi) over right arrow (G) <= 3, and present a complete characterization of unit interval graphs with omega(G)= ?(G) = 3. Then, we show that deciding whether (chi) over right arrow (s)(G) = omega(G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing (chi) over right arrow (s)(G) is FPT when parameterized by the minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing (chi) over right arrow (s)(G) but also (chi) over right arrow (G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 4(O(k2)) and O(2(k)k(2)), in chordal graphs and split graphs, respectively, for the problem of deciding whether (chi) over right arrow (s)(G) = k parameterized by k. We also present exponential kernels for computing both (chi) over right arrow (G) and (chi) over right arrow (s)(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing (chi) over right arrow (s)(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP subset of coNP/poly. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0)