2026-02-262026-02-262025-07COELHO, Erika Morais Martins et al. The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids. Discrete Applied Mathematics, [s. l.], v. 369, p. 96-109, 2025. DOI: 10.1016/j.dam.2025.03.001. Disponível em: https://www.sciencedirect.com/science/article/abs/pii/S0166218X25001258. Acesso em: 18 fev. 2026.0166-218Xe- 1872-6771https://www.sciencedirect.com/science/article/abs/pii/S0166218X25001258An oriented k-coloring of an oriented graph G ⃗ = ( V, A ) 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 classes have the same orientation. The smallest k such that G ⃗ admits an oriented k-coloring is the oriented chromatic number χ o ( G ⃗ ) of G ⃗. The k-oriented chromatic number decision problem asks whether an oriented graph G ⃗ has oriented chromatic number at most k. k-oriented chromatic number is a polynomial problem, when k ≤ 3 and N P-complete, when k ≥ 4 even if input G ⃗ is acyclic and the underlying graph G is bipartite, cubic and planar. In 2003, Fertin, Raspaud and Roychowdhury established exact values and bounds on the oriented chromatic number for several grid subgraph classes. But, the time complexity of k-oriented chromatic number was unknown for grid subgraphs. In this work we prove that the k-oriented chromatic number problem is NP-complete even if G ⃗ is acyclic oriented, k ≥ 4, and the underlying graph G is a connected and subcubic subgraph of a grid.engAcesso RestritoArtigo10.1016/j.dam.2025.03.001