The edge density of critical digraphs (Q519953)

The paper studies the \(k\)-critical digraphs \(D\), and determines upper and lower bounds for the edge density of \(k\)-critical digraphs, using the chromatic number of \(D\), the fewest number of colors needed to color the vertices of \(D\) so that each color class induces an independent set, where each color class induces an acyclic subgraph rather than an independent set. It also introduces two constructions that generate infinite families of \(k\)-critical digraphs, including those with arbitrarily large digirth. It starts by providing some known results for the edge density of \(k\)-chromatic undirected graphs, and then formally defines the chromatic number of digraphs and gives several examples of \(3\)-critical digraphs. It is followed by presenting a recursive construction that generates a \(k\)-critical digraph from several \((k - 1)\)-critical digraphs connected via a root vertex, and using this construction to produce an infinite family of dense \(k\)-critical digraphs satisfying certain inequality conditions. Finally, it analyzes properties of circulant tournaments and applies a variant of the Hajós construction to generate an infinite family of sparse \(k\)-critical digraphs satisfying certain inequalities.