Critical digraphs with few vertices

2019/10/06 by Matěj Stehlı́k, Stehlík, Matěj
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1910.02454

openalex publication_date 2019/10/06 · openalex created_date 2019/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Minimum number of arcs in k-critical digraphs with order at most 2k-1
• Vertex-critical graphs far from edge-criticality
• The number of edges in critical strongly connected graphs
• Coloring Δ-Critical Graphs With Small High Vertex Cliques
• On the maximum number of edges in k-critical graphs