The edge density of critical digraphs

• Published in: Combinatorica (Budapest. 1981) 2015-10, Vol.35 (5), p.619-631
• Main Authors: Hoshino, Richard, Kawarabayashi, Ken-ichi
• Format: Article
• Language: English
• Subjects: Combinatorics; Mathematics; Mathematics and Statistics; Original Paper
• ISSN: 0209-9683; 1439-6912
• DOI: 10.1007/s00493-014-2862-4

Let χ( G ) denote the chromatic number of a graph G . We say that G is k -critical if χ( G )= k and χ( H ) < k for every proper subgraph H ⊂ G . Over the years, many properties of k -critical graphs have been discovered, including improved upper and lower bounds for || G ||, the number of edges in a k -critical graph, as a function of | G |, the number of vertices. In this note, we analyze this edge density problem for directed graphs, where the chromatic number χ( D ) of a digraph D is defined to be the fewest number of colours needed to colour the vertices of D so that each colour class induces an acyclic subgraph. For each k ≥ 3, we construct an infinite family of sparse k -critical digraphs for which and an infinite family of dense k -critical digraphs for which . One corollary of our results is an explicit construction of an infinite family of k -critical digraphs of digirth l , for any pair of integers k , l ≥3. This extends a result by Bokal et al. who used a probabilistic approach to demonstrate the existence of one such digraph.