Cordero-Michel, Narda; Galeana-Sánchez, Hortensia New bounds for the dichromatic number of a digraph. (English) Zbl 1483.05060 Discrete Math. Theor. Comput. Sci. 21(2019-2020), No. 1, Paper No. 7, 14 p. (2019). J. A. Bondy [J. Lond. Math. Soc., II. Ser. 14, 277–282 (1976; Zbl 0344.05124)] proved that the chromatic number of a digraph \(D\) is at most its circumference, the length of a longest cycle. Notice that any proper coloring of a loopless digraph \(D\) gives adjacent vertices different colors, so it is also an acyclic coloring and thus the chromatic number is an upper bound for the dichromatic number of \(D\). In this way, the circumference is also an upper bound for \(\chi_A (D)\).The dichromatic number of a digraph \(D\), denoted by \(\chi_A (D)\), is the minimum \(k\) such that \(D\) admits a \(k\)-coloring of its vertex set in such a way that each color class is acyclic.In this paper, the authors show that if they have more information about the lengths of cycles in a digraph, then they can improve the bounds for the dichromatic number known until now. Reviewer: Dara Moazzami (Tehran) Cited in 1 Document MSC: 05C15 Coloring of graphs and hypergraphs 05C20 Directed graphs (digraphs), tournaments 05C35 Extremal problems in graph theory 05C12 Distance in graphs Keywords:directed graph; acyclic coloring; DFS algorithm Citations:Zbl 0344.05124 PDFBibTeX XMLCite \textit{N. Cordero-Michel} and \textit{H. Galeana-Sánchez}, Discrete Math. Theor. Comput. Sci. 21, No. 1, Paper No. 7, 14 p. (2019; Zbl 1483.05060) Full Text: arXiv Link