The complexity of arc-colorings for directed hypergraphs Original Research Article

We address some complexity questions related to the arc-coloring of directed hypergraphs. Such hypergraphs arise as a generalization of digraphs, by allowing the tail of each arc to consist of more than one node. The related arc-coloring extends the notion of digraph arc-coloring, which has been studied by diverse authors. Using two classical results we easily prove that the optimal coloring of a digraph, as well as the 2-coloring test for every directed hypergraph, require polynomial time. Instead, the k-colorability problem for some fixed degree d is shown to be NP-complete if k⩾d⩾2 and k⩾3, even if the input is restricted to the so-called non-overlapping hypergraphs. We also describe a sub-class of hypergraphs for which the 3-colorability test is polynomially decidable. Some results are rephrased and proved using suitable adjacency matrices, namely walls.