  We consider acyclic r-colorings in graphs and digraphs: they color the
vertices in r colors, each of which induces an acyclic graph or digraph. (This
includes the dichromatic number of a digraph, and the arboricity of a graph.)
For any girth and sufficiently high degree, we prove the NP-completeness of
acyclic r-colorings; our method also implies the known analogue for classical
colorings. The proofs use high girth graphs with high arboricity and
dichromatic numbers. High girth graphs and digraphs with high chromatic and
dichromatic numbers have been well studied; we re-derive the results from a
general result about relational systems, which also implies the similar fact
about high girth and high arboricity used in the proofs. These facts concern
graphs and digraphs of high girth and low degree; we contrast them by
considering acyclic colorings of tournaments (which have low girth and high
degree). We prove that even though acyclic two-colorability of tournaments is
known to be NP-complete, random acyclically r-colorable tournaments allow
recovering an acyclic r-coloring in deterministic linear time, with high
probablity.
