Proper Orientations of Chordal Graphs - Araujo, Julio; Cezar, Alexandre; Lima, Carlos Vinícius Gomes Costa; dos Santos, Vinicius Fernandes; Silva, Ana Shirley Ferreira (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da Computação, 2020)
An orientation D of a graph G = (V, E) is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each v ∈ V(G), the indegree of v in D, denoted by d D − (v), is the number of arcs with head v in D. An orientation D of G is proper if d D − (u) ≠ d D − (v), for all uv ∈ E(G). An orientation with maximum indegree at most k is called a k-orientation. The proper orientation number of G, denoted by χ → (G), is the minimum integer k such that G admits a proper k-orientation. We prove that determining whether χ → (G) ≤ k is NP-complete for chordal graphs of bounded diameter. We also present a tight upper bound for χ → (G) on split graphs and a linear-time algorithm for quasi-threshold graphs.