Various bounds on the minimum number of arcs in a $k$-dicritical digraph

Abstract

The dichromatic number $\vec{\chi }(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vec{\chi }(G)=k$ and each proper subgraph $H$ of $G$ satisfies $\vec{\chi }(H)\le k-1$. %An oriented graph is a digraph with no cycle of length $2$. We prove various bounds on the minimum number of arcs in a $k$-dicritical digraph, a structural result on $k$-dicritical digraphs and a result on list-dicolouring. We characterise $3$-dicritical digraphs $G$ with $(k-1)|V(G)|+1$ arcs. For $k\ge 4$, we characterise $k$-dicritical digraphs $G$ on at least $k+1$ vertices and with $(k-1)|V(G)|+k-3$ arcs, generalising a result of Dirac. We prove that, for $k\ge 5$, every $k$-dicritical digraph $G$ has at least $(k-1/2-1/(k-1))|V(G)|-k(1/2-1/(k-1))$ arcs, which is the best known lower bound. We prove that the number of connected components induced by the vertices of degree $2(k-1)$ of a $k$-dicritical digraph is at most the number of connected components in the rest of the digraph, generalising a result of Stiebitz. Finally, we generalise a Theorem of Thomassen on list-chromatic number of undirected graphs to list-dichromatic number of digraphs.