TY - JOUR

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

AU - Kostochka, Alexandr V.

AU - Stiebitz, Michael

N1 - Funding Information:
Research supported in part by the Simons Visiting Professor, by NSF grant DMS-1600592, and by grants 18-01-00353 and 19-01-00682 of the Russian Foundation for Basic Research.
Publisher Copyright:
© 2020, Springer Japan KK, part of Springer Nature.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/5/1

Y1 - 2020/5/1

N2 - 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.

AB - 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.

KW - Average degree

KW - Coloring graphs and digraphs

KW - Critical graphs and digraphs

UR - http://www.scopus.com/inward/record.url?scp=85079708121&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85079708121&partnerID=8YFLogxK

U2 - 10.1007/s00373-020-02147-y

DO - 10.1007/s00373-020-02147-y

M3 - Article

AN - SCOPUS:85079708121

VL - 36

SP - 703

EP - 718

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 3

ER -