On the Proper Orientation Number of Chordal Graphs

• Júlio Araújo UFC
• Alexandre Cezar UFC
• Carlos V. G. C. Lima UFCA
• Vinicius F. dos Santos UFMG
• Ana Silva UFC

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

Abstract

An orientation $D$ of a simple graph $G=(V,E)$ is proper if~$u$ and~$v$ have distinct indegrees, whenever~$uv \in E$. The proper orientation number of a graph $G$ is the smallest positive integer $k$ such that $G$ has a proper orientation~$D$ with maximum indegree equal to $k$, denoted by $\po(G)$. We prove that deciding whether $\po(G)\leq k$ is \FPT, parameterized by $k$, when restricted to chordal graphs, present an exponential kernel to this class and prove that no polynomial kernel may exist, unless $\NP\subseteq \coNP/\poly$. We also present improved kernels for split and cobipartite graphs. Furthermore, we provide bounds for subclasses of chordal graphs, like block and outerplanar chordal graphs, and for cographs.

Keywords: proper orientation, chordal graphs, complexity

References

Ahadi, A. and Dehghan, A. (2013). The complexity of the proper orientation number.Information Processing Letters, 113(19):799–803.

Araujo, J., Cezar, A., Lima, C., dos Santos, V., and Silva, A. S. (2020a). Proper orien-tations of chordal graphs. InAnais do V Encontro de Teoria da Computação, pages21–24, Porto Alegre, RS, Brasil. SBC.

Araujo, J., Cezar, A., Lima, C. V. G. C., dos Santos, V. F., and Silva, A. (2020b). On the proper orientation number of chordal graphs.

Araujo, J., Cohen, N., de Rezende, S. F., Havet, F., and Moura, P. F. (2015). On the proper orientation number of bipartite graphs. Theoretical Computer Science, 566(0):59–75.

Araujo, J., Havet, F., Sales, C. L., and Silva, A. (2016). Proper orientation of cacti.Theoretical Computer Science, 639:14–25.

Araujo, J., Sales, C. L., Sau, I., and Silva, A. (2019). Weighted proper orientations oftrees and graphs of bounded treewidth.Theoretical Computer Science, 771:39–48.

Bondy, J. A. and Murty, U. S. R. (2008).Graph theory, volume 244 ofGraduate Texts inMathematics. Springer-Verlag London.

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk,M., and Saurabh, S. (2015).Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.

Drucker, A. (2012). New limits to classical and quantum instance compression. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 609–618. IEEE Computer Society.

Fomin, F. V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019).Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.

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.

Knox, F., Matsumoto, N., de la Maza, S. G. H., Mohar, B., and Sales, C. L. (2017). Proper orientations of planar bipartite graphs. Graphs and Combinatorics, 33:1189–1194.