Hajós and ore constructions for digraphs

Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

15 Downloads (Pure)


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 Kk ’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.

TidsskriftElectronic Journal of Combinatorics
Udgave nummer1
Antal sider22
StatusUdgivet - 20. mar. 2020


Dyk ned i forskningsemnerne om 'Hajós and ore constructions for digraphs'. Sammen danner de et unikt fingeraftryk.