Proper Orientations of Chordal Graphs
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 dD−(v), is the number of arcs with head v in D. An orientation D of G is proper if dD−(u) ≠ dD−(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.
Ahadi, A., Dehghan, A., and Saghafian, M. (2017). Is there any polynomial upper boundfor the universal labeling of graphs? J. Combin. Optim., 34(3):760–770.
Ai, J., Gerke, S., Gutin, G., Shi, Y., and Taoqiu, Z. Proper orientation number of triangle-free bridgeless outerplanar graphs. J. Graph Theor., to appear.
Araujo, J., Cohen, N., de Rezende, S. F., Havet, F., and Moura, P. F. (2015). On the proper orientation number of bipartite graphs. Theor. Comput. Sci., 566(0):59–75.
Araujo, J., Havet, F., Sales, C. L., and Silva, A. (2016). Proper orientation of cacti. Theor.Comput. Sci., 639:14–25.
Araujo, J., Sales, C. L., Sau, I., and Silva, A. (2019). Weighted proper orientations of trees and graphs of bounded treewidth. Theor. Comput. Sci., 771:39–48.
Bertossi, A. A. (1984). Dominating sets for split and bipartite graphs. Inform. Process. Lett., 19(1):37–40.
Dehghan, A. (2019). On the semi-proper orientations of graphs. CoRR, abs/1905.02867.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Jing-Ho, Y., Jer-Jeong, C., and Chang, G. J. (1996). Quasi-threshold graphs. Discrete Appl. Math., 69(3):247–255.
Knox, F., Matsumoto, N., de la Maza, S. G. H., Mohar, B., and Sales, C. L. (2017). Proper orientations of planar bipartite graphs. Graph. Combinator., 33:1189–1194.
Raman, V. and Saurabh, S. (2008). Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica, 52(2):203–225.