## Abstract

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.

Original language | English |
---|---|

Article number | P1.63 |

Journal | The Electronic Journal of Combinatorics |

Volume | 27 |

Issue number | 1 |

Number of pages | 22 |

ISSN | 1077-8926 |

DOIs | |

Publication status | Published - 20. Mar 2020 |