Otro(a)s Autore(a)s
Araújo J.
Havet F.
Linhares Sales C.
Nisse N.
Año
2025

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 χ⃗(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,w)(v)≠S(D,w)(u), where S(D,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 maxv∈V(G)S(D,w)(v)≤k. The semi-proper orientation number of a graph G, denoted by χs⃗(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that χs⃗(G)∈{ω(G)−1,ω(G)} for every split graph G, and that, given a split graph G, deciding whether χs⃗(G)=ω(G)−1 is an NP-complete problem. We also show that, for every k, there exist a (chordal) graph G and a split subgraph H of G such that χ⃗(G)≤k and χ⃗(H)=2k−2. In the sequel, we show that, for every n≥p(p+1), χs⃗(Pnp)=[Formula presented]p, where Pnp 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 ω(G)=3, and present a complete characterization of unit interval graphs with χ⃗(G)=ω(G)=3. Then, we show that deciding whether χs⃗(G)=ω(G)−1 can be solved in polynomial time in the class of cobipartite graphs. Finally, we prove that computing χ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 χs⃗(G), but also χ⃗(G), admits a polynomial kernel when parameterized by the neighborhood diversity plus the value of the solution. These results imply kernels of size 4O(k and O(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether χs⃗(G)≤k parameterized by k. We also present exponential kernels for computing both χ⃗(G) and χs⃗(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing χs⃗(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP⊆coNP/poly.

Referencia
Araújo J., Havet F., Linhares Sales C., Nisse N., Suchan K. (2025). Semi-proper orientations of dense graphs., Discrete Applied Mathematics, 371, 196–217.
Artículo