The complexity of arc-colorings for directed hypergraphs
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.
05b99 05c15 05c20 68q17