Hajós and Ore constructions for digraphs (Q2309234): Difference between revisions

Summary: The dichromatic number \(\overrightarrow{\chi}(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 \(\overrightarrow{\chi}(D) = k\) but \(\overrightarrow{\chi}(D^\prime) < k\) for all proper subdigraphs \(D^\prime\) 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 \textit{A. Urquhart} [J. Graph Theory 26, No. 4, 211--215 (1997; Zbl 0886.05067)] 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\).