A digraph is $3$-dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that the collection of 3-dicritical semi-complete digraphs is finite. Further, we give a computer-assisted proof of a full characterization of 3-dicritical semi complete digraphs. There are eight such digraphs, two of which are tournaments. We finally give a general upper bound on the maximum number of arcs in a $3$-dicritical digraph.
@article{10_37236_12820,
author = {Fr\'ed\'eric Havet and Florian H\"orsch and Lucas Picasarri-Arrieta},
title = {The 3-dicritical semi-complete digraphs},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12820},
zbl = {1556.05056},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12820/}
}
TY - JOUR
AU - Frédéric Havet
AU - Florian Hörsch
AU - Lucas Picasarri-Arrieta
TI - The 3-dicritical semi-complete digraphs
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12820/
DO - 10.37236/12820
ID - 10_37236_12820
ER -
%0 Journal Article
%A Frédéric Havet
%A Florian Hörsch
%A Lucas Picasarri-Arrieta
%T The 3-dicritical semi-complete digraphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12820/
%R 10.37236/12820
%F 10_37236_12820
Frédéric Havet; Florian Hörsch; Lucas Picasarri-Arrieta. The 3-dicritical semi-complete digraphs. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12820
