Critical digraphs with few vertices
Matěj Stehlı́k · arXiv (Cornell University) · 2019
We show that every k-dichromatic vertex-critical digraph on at most 2k-2 vertices has a disconnected complement. This answers a question of Bang-Jensen et al., and generalises a classical theorem of Gallai on undirected vertex-critical graphs.