Let G → = (V,A) be an oriented graph, G = (V,E) the underlying graph of G → and k be a positive integer. An oriented k-coloring of G → is a partition of V into k subsets, such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The oriented chromatic number χ ° (G → ) of G → is the smallest k , such that G → admits an oriented k -coloring. The oriented chromatic number of G, denoted by χ ° (G), is the maximum of χ ° (G → ) for all orientations G → of G . Given two graphs G and H with V(G) n V(H) = θ, we say that G U H is the disjoint union graph of G and H , if V(G U H) = V(G) U V(H) and E(G U H) = E(G) U E(H). A wheel graph W q ,q ≥ 3 has V(W q ) = {v1, v2, ... ,v q ,c} and E(Wq) = {v i -v i+1 : i ε {1,2,...,q- 1}} U { v q v 1 } U { v i c : i ε {1,2,...,q}}. Wheel graphs consist of a important class having many theoretical and algorithmic applications with an ample literature on coloring problems. Bounds for the oriented coloring of wheel graphs were evaluated on the literature, but the exact values were not known. In this paper we determine the exact value of χ o (W q ) as q + 1 when 3 ≤ q ≤ 6, 7 whether q =7 and 8 whether q ≥ 8, producing a linear time algorithm to color any wheel graph. Let K p be the complete graph with p ≥ 1 vertices, when q ≤ 8 we give exact values for χ o (K p U W q ) and for large values of q ≥ 9 we show that χ o (K p U W q ) is either p + 2 or p + 3.

Let ⃗G = (V, A) be an oriented graph. An oriented k-coloring of ⃗G is a partition of V into k color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest k such that ⃗G admits an oriented k-coloring is the oriented chromatic number Xo(⃗G) = k of ⃗G. In an oriented coloring of ⃗G every pair of vertices with oriented distance at most 2 in ⃗G have different colors. In 2004, Klostermeyer and MacGillivray defined the concept of an “analogue of clique” for oriented coloring in which a subgraph ⃗H of ⃗G is an oriented clique if every pair of vertices of ⃗H is in an oriented distance of at most 2 in ⃗H. The authors defined the absolute oriented clique number of ⃗G as the number of vertices |V(H)| = ωao(⃗G) of the largest oriented clique ⃗H of ⃗G and satisfies that ωao(⃗G) ≤ Xo(⃗G). Ever since, for almost 20 years, the time complexity status of this parameter remained unknown. The relative oriented clique number ωao(⃗G) of an oriented graph ⃗G is the size of the largest set of vertices R, such that every pair of vertices of R is at a maximum oriented distance of 2 in R. For every oriented graph ⃗G, ωao(⃗G) ≤ ωro(⃗G) ≤ Xo(⃗G). In this paper we classify Absolute Oriented Clique - the Klostermeyer and Mac Gillivray's decision problem - proving that given an oriented graph ⃗G and a positive integer k it is NP-complete to decide whether ωao(⃗G) ≥ k. We prove that for all ε > 0, there is no polynomial-time approximation for Relative Oriented Clique and for Absolute Oriented Clique within a factor of n1_ε, unless P = NP. Finally, we prove that Relative Oriented Clique is W[1]-complete and that Absolute Oriented Clique belongs to W[2] and is W[1]-hard.