A Cvetković-type theorem for coloring of digraphs (Q2052174)

A \(k\)-coloring of a digraph is a partition of the digraph into \(k\) sets. A \(k\)-coloring is said to be proper if each color class is acyclic. A digraph is \(k\)-colorable if it has a proper \(k\)-coloring. The chromatic number of a digraph is the minimum number \(k\) such that the digraph is \(k\)-colorable. It has been shown that if a graph is an \(n\)-vertex simple graph with the chromatic number \(k\), then its spectral radius is at most the spectral radius of the \(n\)-vertex balanced complete \(k\)-partite graph, yielding a certain bound. The question was whether or not this bound can be extended to digraphs. The purpose of this paper is to show that by analyzing the characteristic polynomial of a digraph, a tight upper bound for the spectral radius of the digraph can be found in terms of the number of vertices and the chromatic number of the digraph. It also characterizes when equality holds, thereby providing a simple proof of an early result.