Hajós and ore constructions for digraphs

The dichromatic number^→χ(D) of a digraph D is the minimum number of colors needed to color the vertices of D such that each color class induces an acyclic subdigraph of D. A digraph D is k-critical if^→χ(D) = k but^→χ(D^′) < k for all proper subdigraphs D^′ of D. We examine methods for creating infinite families of critical digraphs, the Dirac join and the directed and bidirected Hajós join. We prove that a digraph D has dichromatic number at least k if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on k vertices by directed Hajós joins and identifying non-adjacent vertices. Building upon that, we show that a digraph D has dichromatic number at least k if and only if it can be constructed from bidirected K_k ’s by using directed and bidirected Hajós joins and identifying non-adjacent vertices (so called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree k − 1 and out-degree k − 1 in D.