The absolute oriented clique number problem is NP-complete

• E. M. M. Coelho UFG
• H. Coelho UFG
• L. Faria UERJ
• M. P. Ferreira UFG
• S. Klein UFRJ

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

Abstract

Let G = (V, A) be an oriented graph. The oriented chromatic number of G denoted by χ_o(G) is a well-know parameter in the literature. The absolute oriented clique number, ω_ao(G), is the order of the largest subgraph H of G such that χ_o(H) = |V(H)|. In this work we show that deciding if ω_ao(G) ≤ k is an NP-complete problem and there is no polynomial-time approximation within a factor of n^{{1 - ε}} for all ε > 0, unless P = NP.

Keywords: Oriented Graph, Oriented Clique Number, Oriented Chromatic Number

References

Courcelle, B. (1994). The monadic second order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54(2-3):117–149.

Das, S., Prabhu, S., e Sen, S. (2018). A study on oriented relative clique number. Discrete Mathematics, 341(7):2049–2057.

Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability, volume 174. Freeman San Francisco.

Klostermeyer, W. e MacGillivray, G. (2004). Analogues of cliques for oriented coloring. Discussiones Mathematicae Graph Theory, 24(3):373–387.

Raspaud, A. e Sopena, E. (1994). Good and semi-strong colorings of oriented planar graphs. Information Processing Letters, 51(4):171–174.

Sopena, É. (2016). Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math., 339(7):1993–2005.

Zuckerman, D. (2006). Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690.