Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph

Pierre Aboulker ; Quentin Vermande¹

¹ENS/PSL

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

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) \leq k-1$. 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 \geq 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 \geq 5$, every $k$-dicritical digraph $G$ has at least $(k-\frac 1 2 - \frac 1 {k-1}) |V(G)| - k(\frac 1 2 - \frac 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.

Détail

DOI : 10.37236/11549

Classification : 05C30, 05C20, 05C35, 05C40
Mots-clés : critical \(k\)-chromatic graphs, minor-vertices, number of connected components