On the minimum number of arcs in 4‐dicritical oriented graphs
- 29 July 2024
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 107 (4) , 778-809
Abstract
The dichromatic number of a digraph is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph is ‐dicritical if and each proper subdigraph of satisfies . For integers and , we define (resp., ) as the minimum number of arcs possible in a ‐dicritical digraph (resp., oriented graph). Kostochka and Stiebitz have shown that . They also conjectured that there is a constant such that for and large enough. This conjecture is known to be true for . In this work, we prove that every 4‐dicritical oriented graph on vertices has at least arcs, showing the conjecture for . We also characterise exactly the 4‐dicritical digraphs on vertices with exactly arcs.Keywords
Funding Information
- Agence Nationale de la Recherche
This publication has 12 references indexed in Scilit:
- On the Minimum Number of Arcs in \(\boldsymbol{k}\)-Dicritical Oriented GraphsSIAM Journal on Discrete Mathematics, 2024
- On the Minimum Number of Arcs in 4-Dicritical Oriented Graphs2023
- Structure in sparse k-critical graphsJournal of Combinatorial Theory, Series B, 2022
- The Minimum Number of Edges in 4-Critical Digraphs of Given OrderGraphs and Combinatorics, 2020
- A Brooks-Type Result for Sparse Critical GraphsCombinatorica, 2018
- On the minimum number of edges in triangle-free 5-critical graphsEuropean Journal of Combinatorics, 2017
- Ore's conjecture on color-critical graphs is almost trueJournal of Combinatorial Theory, Series B, 2014
- Gallai's Theorem for List Coloring of DigraphsSIAM Journal on Discrete Mathematics, 2011
- On the Number of Edges in Colour-Critical Graphs and HypergraphsCombinatorica, 2000
- A Theorem of R. L. Brooks and a Conjecture of H. HadwigerProceedings of the London Mathematical Society, 1957