Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints

Tom\' as Feder, Pavol Hell, Carlos Subi

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 numbe…