The diachromatic number of digraphs

Abstract

We consider the extension to directed graphs of the concept of the achromaticnumber in terms of acyclic vertex colorings. The achromatic number has beenintensely studied since it was introduced by Harary, Hedetniemi and Prins in 1967.The dichromatic number is a generalization of the chromatic number for digraphsdefined by Neumann-Lara in 1982. A coloring of a digraph is an acyclic coloringif each subdigraph induced by each chromatic class is acyclic, and a coloring iscomplete if for any pair of chromatic classesx, y, there is an arc fromxtoyand anarc fromytox. The dichromatic and diachromatic numbers are, respectively, thesmallest and the largest number of colors in a complete acyclic coloring. We givesome general results for the diachromatic number and study it for tournaments. Wealso show that the interpolation property for complete acyclic colorings does holdand establish Nordhaus-Gaddum relations.