Proper Orientations of Chordal Graphs

• Julio Araujo UFC
• Alexandre Cezar UFC
• Carlos Vinícius Gomes Costa Lima UFC
• Vinicius Fernandes dos Santos UFMG
• Ana Shirley Ferreira Silva UFC

DOI: https://doi.org/10.5753/etc.2020.11080

Resumo

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.

Palavras-chave: Graph Theory, Coloring, Orientation, Computational Complexity, Chordal graphs

Referências

Ahadi, A. and Dehghan, A. (2013). The complexity of the proper orientation number. Inform. Process. Lett., 113(19):799–803.

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.