The diachromatic number of digraphs (Q1784278)

Summary: We consider the extension to directed graphs of the concept of achromatic number in terms of acyclic vertex colorings. The achromatic number have been intensely studied since it was introduced by \textit{F. Harary} et al. [Port. Math. 26, 453--462 (1967; Zbl 0187.20903)]. The dichromatic number is a generalization of the chromatic number for digraphs defined by \textit{V. Neumann-Lara} [J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. A coloring of a digraph is an acyclic coloring if each subdigraph induced by each chromatic class is acyclic, and a coloring is complete if for any pair of chromatic classes \(x,y\), there is an arc from \(x\) to \(y\) and an arc from \(y\) to \(x\). The dichromatic and diachromatic numbers are, respectively, the smallest and the largest number of colors in a complete acyclic coloring. We give some general results for the diachromatic number and study it for tournaments. We also show that the interpolation property for complete acyclic colorings does hold and establish Nordhaus-Gaddum relations.