## Abstract

The dichromatic number χ(D) of a digraph D, introduced by Neumann-Lara in the 1980s, is the least integer k for which D has a coloring with k colors such that each vertex receives a color and no directed cycle of D is monochromatic. The digraphs considered here are finite and may have antiparalell arcs, but no parallel arcs. A digraph D is k-critical if each proper subdigraph D^{′} of D satisfies χ(D^{′}) < χ(D) = k. For integers k and n, let d_{k}(n) denote the minimum number of arcs possible in a k-critical digraph of order n. It is easy to show that d_{2}(n) = n for all n≥ 2 , and d_{3}(n) ≥ 2 n for all possible n, where equality holds if and only if n is odd and n≥ 3. As a main result we prove that d_{4}(n) ≥ ⌈ (10 n- 4) / 3 ⌉ for all n≥ 4 and n≠ 5 where equality holds if n≡1(mod3) or n≡2(mod3). As a consequence, we obtain that for each surface S the number of 4-critical oriented graphs that can be embedded on S is finite.

Original language | English (US) |
---|---|

Pages (from-to) | 703-718 |

Number of pages | 16 |

Journal | Graphs and Combinatorics |

Volume | 36 |

Issue number | 3 |

DOIs | |

State | Published - May 1 2020 |

## Keywords

- Average degree
- Coloring graphs and digraphs
- Critical graphs and digraphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics