Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors

Abstract

The dichromatic and diachromatic numbers of a digraph are the minimum and maximum numbers of colors, respectively, in acyclic and complete colorings of the digraph. In this paper, we construct, for all $r\le t$, non-symmetric digraphs with dichromatic number $r$ and diachromatic number $t$. Moreover, we discuss the existence of asymmetric digraphs with dichromatic number $r$ and diachromatic number $t\ge r$, establishing a quadratic upper bound $b(r)\le t$.

9 pages, 2 figures