The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids

Abstract

An 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.