On the minimum number of arcs in k-dicritical oriented graphs

Abstract: The dichromatic number

d i c (D)

of a digraph

D

is the least integer

k

such that

D

can be partitioned into

k

directed acyclic digraphs. A digraph is

k

-dicritical if

d i c (D) = k

and each proper subgraph

D^{'}

of

D

satisfies

d i c (D^{'}) l e q k - 1

. An oriented graph is a digraph with no directed cycle of length

2

. For integers

k

and

n

, we denote by

o_{k} (n)

the minimum number of edges of a

k

-critical oriented graph on

n

vertices (with the convention

o_{k} (n) = + i n f t y

if there is no

k

-dicritical oriented graph of order

n

). The main result of this paper is a proof that

o_{3} (n) g e q f r a c 7 n + 2 3

together with a construction witnessing that

o_{3} (n) l e q l e f t l c e i l f r a c 5 n 2 i g h t c e i l

for all

n g e q 12

. We also give a construction showing that for all sufficiently large

n

and all

k g e q 3

,

o_{k} (n) < (2 k - 3) n

, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all

k g e q 2

,

o_{k} (n) g e q p t h k - f r a c 34 - f r a c 1 4 k - 6 n + f r a c 3 4 (2 k - 3)

, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.

This page was built for publication: On the minimum number of arcs in $k$-dicritical oriented graphs