The Minimum Number of Edges in 4-Critical Digraphs of Given Order

Alexandr V. Kostochka, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review

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 dk(n) denote the minimum number of arcs possible in a k-critical digraph of order n. It is easy to show that d2(n) = n for all n≥ 2 , and d3(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 d4(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 languageEnglish (US)
Pages (from-to)703-718
Number of pages16
JournalGraphs and Combinatorics
Volume36
Issue number3
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'The Minimum Number of Edges in 4-Critical Digraphs of Given Order'. Together they form a unique fingerprint.

Cite this