zbMATH — the first resource for mathematics

Dichromatic number, circulant tournaments and Zykov sums of digraphs. (English) Zbl 0984.05043
Author’s abstract: The dichromatic number \(\text{dc}(D)\) of a digraph \(D\) is the smallest number of colors needed to color the vertices of \(D\) so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov sum of digraphs over a digraph \(D\) is reduced to that of computing a multicovering number of a hypergraph \(H_1(D)\) associated to \(D\) in a natural way. This result allows us to construct an infinite family of pairwise non-isomorphic vertex-critical \(k\)-dichromatic circulant tournaments for every \(k\geq 3\), \(k\neq 7\).

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
Full Text: DOI Link